<|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.




The image above shows a figure with height 7 and width 9 and containing two spots.

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 .
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;

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

    int T;
    cin >> T;

    for (int tc = 0; tc < T; tc++) {
        int H, W, N;
        cin >> H >> W >> N;

        // Print empty line between test cases as required
        if (tc) cout << "\n";

        // Count how many interior cells belong to each checkerboard parity.
        // Interior means not on the border, because border white cells connect
        // to the infinite outside white region -> not finite -> not a "spot".
        int count[2] = {0, 0};
        for (int i = 1; i <= H - 2; i++) {
            for (int j = 1; j <= W - 2; j++) {
                count[(i + j) & 1]++;
            }
        }

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

        // Choose parity with more available interior positions
        int parity = (count[0] >= count[1]) ? 0 : 1;

        // Prepare list of all candidate interior cells of that parity
        vector<pair<int,int>> pos;
        pos.reserve(maxSpots);
        for (int i = 1; i <= H - 2; i++) {
            for (int j = 1; j <= W - 2; j++) {
                if (((i + j) & 1) == parity) {
                    pos.push_back({i, j});
                }
            }
        }

        // Start with all black: black cells are '.', white are '#'
        vector<string> grid(H, string(W, '.'));

        // Place N isolated white cells in the interior.
        // Because we use one checkerboard parity, no two chosen cells share a side,
        // thus each is a separate 4-connected white component => a spot.
        for (int k = 0; k < N; k++) {
            auto [i, j] = pos[k];
            grid[i][j] = '#';
        }

        // Output the resulting grid
        for (int i = 0; i < H; i++) {
            cout << grid[i] << "\n";
        }
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

def solve_case(H: int, W: int, N: int) -> str:
    # Count interior cells by checkerboard parity.
    # Only interior can host finite white components (spots).
    count = [0, 0]
    for i in range(1, H - 1):
        for j in range(1, W - 1):
            count[(i + j) & 1] += 1

    max_spots = max(count)
    if N > max_spots:
        return "Impossible"

    # Choose parity with more available positions
    parity = 0 if count[0] >= count[1] else 1

    # Collect interior cells of that parity
    positions = []
    for i in range(1, H - 1):
        for j in range(1, W - 1):
            if ((i + j) & 1) == parity:
                positions.append((i, j))

    # Start with all black '.' (black figure background)
    grid = [list("." * W) for _ in range(H)]

    # Turn N of those cells to white '#'
    # Each chosen cell is isolated in 4-neighbour sense => each is one spot.
    for k in range(N):
        i, j = positions[k]
        grid[i][j] = "#"

    return "\n".join("".join(row) for row in grid)

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

    outputs = []
    for _ in range(t):
        H = int(data[idx]); W = int(data[idx + 1]); N = int(data[idx + 2])
        idx += 3
        outputs.append(solve_case(H, W, N))

    # Empty line between test cases
    sys.stdout.write("\n\n".join(outputs))

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

This construction matches the editorial idea: create exactly `N` finite white 4-components (spots) by placing isolated interior white cells, while keeping all black cells 8-connected.