Statement

This must be an easy task, because it only deals with a few zeros and ones, and we even placed it first in the problem set.

You will be given a positive integer \(n\).

Your task is to construct any one grid of \(n\times n\) zeros and ones with the following properties:

• In each row and each column, the number of 0s and the number of 1s differ by at most one. (I.e., they differ by 1 if \(n\) is odd and they are equal if \(n\) is even.)

• In each row and each column there are never three consecutive equal values.

• The \(2n\) bit strings obtained by reading each row left to right and each column top to bottom are all mutually distinct.

Input format

The first line of each input file contains the number \(t\) of test cases. The specified number of test cases follows, one after another.

Each test case consists of a single line with a single positive integer \(n\).

Output format

For a test case that contains the integer \(n\), output either:

• one line with the string “IMPOSSIBLE” if there is no grid with the required parameters
• one line with the string “POSSIBLE” followed by \(n\) lines (each containing a string of \(n\) zeros and ones) describing any one valid solution

Subproblem E1 (100 points, public)

Input file: E1.in

There are \(t=35\) test cases, the biggest of them has \(n=500\).

Your score is calculated as follows:

• Your score starts at 0 points.
• If your output cannot be parsed as a plain ASCII text, your score stays at 0 points.
• If your output to the first test case (\(n=7\)) is correct, your score becomes 9 points.
• If your outputs to the first 9 test cases (all values from \(n=1\) to \(n=9\)) are correct, your score becomes 15 points.
• If your outputs to the first 13 test cases (all values from \(n=1\) to \(n=13\)) are correct, your score becomes 24 points.
• If your outputs to the first 20 test cases (\(n\leq 40\)) are correct, your score becomes 62 points.
• If all your outputs are are correct (\(n\leq 500\)), your score becomes 100 points.

Example

2
3
6

IMPOSSIBLE
POSSIBLE
110100
001011
101010
010101
001101
110010

The example input contains \(t=2\) test cases.

The first test case has \(n=3\). Each row and each column of the grid must have two 0s and one 1 or vice versa. As they all have to be mutually distinct, each of the sequences 001, 010, 011, 100, 101 and 110 must appear exactly once. However, there’s obviously no such grid. (One easy argument why: in these strings there are 9 zeros in total, and we cannot have 4.5 zeros in the grid.)

The second test case has \(n=6\). The example output shows one valid \(6\times 6\) grid.

In the above grid:

• Each row and each column contains three 1s and three 0s.
• There is no 111 and no 000 in any row or column.
• The 12 bit strings that are required to be distinct are 110100, 001011, 101010, 010101, 001101, 110010 (those were the rows), 101001, 100101, 011010, 100110, 011001, and 010110 (those were the columns). We can easily verify that these strings are indeed mutually distinct.