<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

490. Figure ans Spots
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Let's consider an infinite sheet of grid paper. Initially all the cells are white and you can paint some of them black.

Two cells are called 8-neigbours if they share a side or a corner. An 8-path between black cells A and B is a sequence of cells X0 = A, X1, ·s, XL-1, XL = B such that all cells in the sequence are black and for all 0 ≤ i < L the cells Xi and Xi+1 are 8-neighbours. A set of black cells is called a figure if there is an 8-path from each of them into each other.

Two cells are called 4-neighbours if they share a side. A 4-path between white cells A and B is a sequence of cells X0 = A, X1, ·s, XL-1, XL = B such that all cells in the sequence are white and for all 0 ≤ i < L the cells Xi and Xi+1 are 4-neigbours. A finite set of white cells is called a  if:
There is a 4-path from each of them into each other.
The previous condition is broken when any other white cell is added to the set.
We say that a figure has the height H and the width W if it fits in a rectangle H rows high and W columns wide, but does not fit in a rectangle H-1 rows high and W columns wide nor in a rectangle H-1 rows high and W columns wide.

Given the numbers H, W and N, construct a figure with height exactly H and width exactly W and containing exactly N spots.

Input
The input file contains several test cases. The first line of the file contains T (1 ≤ T ≤ 100), the number of test cases. Each of the following T lines describes one test case and contains three integers H, W and N (1 ≤ H, W ≤ 20, 1 ≤ N ≤ 200), separated by spaces.

Output
The output file should contain the following data for each test case:
If it is possible to construct a figure with the given parameters, output any of the possible figures as H rows consisting of W characters each; output the character . for a black cell and the character # for a white cell.
If it is impossible to construct the required figure, output a single line containing the word Impossible.
The output data for two different test cases should be separated by an empty line.

Example(s)
sample input
sample output
3
7 9 2
20 20 22
5 5 10
...
Impossible

<|response|>
## 1) Abridged problem statement (concise)

You must output an **H×W** grid where:
- `.` = **black** cell, `#` = **white** cell.
- All **black** cells must form a single **8-connected** component (connected by sides or corners) → this is the "figure".
- A **spot** is a **finite** maximal **4-connected** component of **white** cells (connected only by sides).
  White regions connected to the outside infinite white area are **not** spots.

Given **H, W, N**, construct such a grid with **exactly N spots**, or print `Impossible`.

Print an empty line between test cases.

Constraints: `1 ≤ H, W ≤ 20`, `1 ≤ N ≤ 200`, `T ≤ 100`.

---

## 2) Key observations

1. **Only enclosed white components count as spots.**
   The grid is on an infinite plane of white cells outside your output rectangle.
   Any white cell that touches the border of the H×W output can 4-connect to the outside infinite white area, thus its component is **infinite**, so it **cannot** be a spot.

2. **Therefore, spots must lie strictly inside the border**:
   allowable spot cells are in rows `1..H-2` and cols `1..W-2` (0-indexed).

3. **Easy way to make many spots:**
   Make the board mostly black (`.`), and place **isolated white cells** (`#`) in the interior.
   Each isolated white cell is a separate finite 4-connected component ⇒ **1 spot**.

4. **How to ensure isolation under 4-neighbour adjacency:**
   Use one color of a **checkerboard** on the interior:
   - Cells with the same parity `(i + j) % 2` are never side-adjacent.
   - So if you place white cells only on one parity, every white cell is isolated (4-disconnected).

5. **Maximum achievable spots with this construction:**
   Let `count[0]`, `count[1]` be the number of interior cells of each parity.
   You can place at most `max(count[0], count[1])` isolated interior white cells.
   If `N` is larger → **Impossible**.

6. **Black 8-connectivity ("figure") remains satisfied:**
   We start with all black, then "punch out" isolated white holes.
   Removing isolated cells on a checkerboard parity does not disconnect the remaining black cells under 8-connectivity for this small-grid construction style; the black area stays as one 8-connected component.

---

## 3) Full solution approach

For each test case `(H, W, N)`:

1. Compute interior parity counts:
   - For all `i in [1, H-2]`, `j in [1, W-2]`, increment `count[(i+j)%2]`.

2. If `N > max(count[0], count[1])`, print `Impossible`.

3. Otherwise choose parity `p` with larger count (ties arbitrary).

4. Build grid of size `H×W` initialized with black `.` everywhere.

5. Collect all interior positions with `(i+j)%2 == p` into a list, and set the first `N` of them to white `#`.

6. Print the grid. Print a blank line between test cases.

Complexity: `O(HW)` per test case (at most 400 cells), trivial within limits.

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int h, w, n;

void read() { cin >> h >> w >> n; }

void solve() {
    // The solution here is fairly simple after understanding the problem
    // statement. We want to have exactly n white connected component, but
    // instead for a h x w grid, we can try to see what's the largest number of
    // components and then fill some of them down to n with black cells. The key
    // observation is that in the white connected components we don't consider
    // diagonal neigbours, meaning we can try a chess board. There are two
    // candidates for a chess board, and we choose the one with more white
    // cells. We only place on inner positions (skip the border) because a
    // white cell on the border would connect to the infinite white exterior
    // and not form a finite spot.

    static bool first = true;
    if(!first) {
        cout << '\n';
    }
    first = false;

    array<int, 2> count = {0, 0};
    for(int i = 1; i < h - 1; i++) {
        for(int j = 1; j < w - 1; j++) {
            count[(i + j) % 2]++;
        }
    }

    int max_n = max(count[0], count[1]);
    if(n > max_n) {
        cout << "Impossible\n";
        return;
    }

    int p_choose = count[0] >= count[1] ? 0 : 1;

    vector<pair<int, int>> positions;
    for(int i = 1; i < h - 1; i++) {
        for(int j = 1; j < w - 1; j++) {
            if((i + j) % 2 == p_choose) {
                positions.emplace_back(i, j);
            }
        }
    }

    vector<string> grid(h, string(w, '.'));
    for(int k = 0; k < n; k++) {
        grid[positions[k].first][positions[k].second] = '#';
    }

    for(auto& row: grid) {
        cout << row << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

def solve_case(h: int, w: int, n: int) -> str:
    # We will place isolated WHITE cells '#' on a checkerboard parity inside the border.
    # All other cells will be BLACK '.'.
    #
    # Each chosen '#' will be 4-disconnected from other '#' cells (checkerboard),
    # and since we never place '#' on the border, each such component is finite:
    # thus each is a "spot".

    # Count interior parity cells
    count = [0, 0]
    for i in range(1, h - 1):
        for j in range(1, w - 1):
            count[(i + j) & 1] += 1

    max_n = max(count)
    if n > max_n:
        return "Impossible"

    # Pick parity with more available cells
    p_choose = 0 if count[0] >= count[1] else 1

    # Collect all interior positions of that parity
    positions = []
    for i in range(1, h - 1):
        for j in range(1, w - 1):
            if ((i + j) & 1) == p_choose:
                positions.append((i, j))

    # Start with all black cells '.'
    grid = [list("." * w) for _ in range(h)]

    # Place n white isolated cells '#'
    for k in range(n):
        i, j = positions[k]
        grid[i][j] = "#"

    # Convert grid to lines
    return "\n".join("".join(row) for row in grid)

def main():
    data = sys.stdin.read().strip().split()
    t = int(data[0])
    idx = 1

    out_parts = []
    for _ in range(t):
        h = int(data[idx]); w = int(data[idx + 1]); n = int(data[idx + 2])
        idx += 3
        out_parts.append(solve_case(h, w, n))

    # Separate test cases by one empty line
    sys.stdout.write("\n\n".join(out_parts))

if __name__ == "__main__":
    main()
```
