C. Escape Room
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver is designing an escape room! His current design is a maze with $$$N$$$ different sites, where each of the $$$\frac{N(N-1)}{2}$$$ pairs of sites is directly connected by a bidirectional tunnel.

To make the maze more interesting, each tunnel is locked with one of $$$K$$$ ($$$1 \leq K \leq 10$$$) keys, numbered $$$1, 2, \dots, K$$$. One can only traverse a tunnel between sites $$$i$$$ and $$$j$$$ if they have its corresponding key $$$a_{ij}$$$.

Additionally, Busy Beaver wants to design the maze such that only certain sets of keys let you traverse the entire maze. In particular, there are $$$x_S \in \{0, 1\}$$$ for each subset $$$S \subseteq \{1, 2, \dots, K\}$$$ such that

  • If $$$x_S = 1$$$, it is possible to move between any two sites in the maze using only the keys in $$$S$$$.
  • If $$$x_S = 0$$$, there exists some pair of sites that cannot be accessed from each other using only the keys in $$$S$$$.
Decide whether or not the task is possible. Additionally, if the task is possible, provide any valid construction with at most $$$300$$$ sites.
Input

Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \leq T \leq 300$$$). The description of the test cases follows.

The first line of each test case contains the integer $$$K$$$ ($$$1 \le K \le 10$$$) — the number of keys.

The second line of each test case contains a string $$$x$$$ ($$$|x| = 2^K$$$, $$$x_i \in \{\texttt{0}, \texttt{1}\}$$$) such that for each $$$S$$$, if $$$i = \sum_{t \in S} 2^{t - 1}$$$ then $$$x_S := x_i$$$. Note that the string $$$x$$$ is zero-indexed, that is, $$$0 \leq i \lt 2^K$$$.

It is guaranteed that the sum of $$$2^K$$$ across all test cases is no more than $$$2^{10}$$$.

Output

For each test case, if it is possible to satisfy the given constraints, the first line of output should contain an integer $$$N$$$ ($$$1 \leq N \leq 300$$$) — the number of sites. The $$$i$$$-th of the next $$$N$$$ lines of output should then contain $$$N$$$ integers $$$a_{ij}$$$ ($$$a_{ii} = 0, a_{ij} = a_{ji}, 1 \leq a_{ij} \leq K$$$ for $$$i \neq j$$$), where for $$$i \neq j$$$, the tunnel between sites $$$i$$$ and $$$j$$$ uses key $$$a_{ij}$$$.

If there are multiple solutions, print any of them. Otherwise, if there is no solution, print a single integer $$$-1$$$ instead.

Due to judging constraints, the sum of $$$N^2$$$ over your outputs should not exceed $$$2 \cdot 10^5$$$. It can be shown that this is enough to solve the problem.

Scoring

You will receive $$$20\%$$$ of the points for each subtask if you correctly decide if a solution exists, but your constructions are incorrect. Specifically, in order to receive these points, when a solution does not exist, you must output $$$-1$$$. When a solution exists, you must output some $$$N$$$ ($$$1 \leq N \leq 300$$$) and a matrix $$$a$$$ that meets the specifications of ($$$a_{ii} = 0, a_{ij} = a_{ji}, 1 \leq a_{ij} \leq K$$$ for $$$i \neq j$$$).

There are three subtasks for this problem.

  • ($$$10$$$ points): The sum of $$$2^K$$$ across all test cases does not exceed $$$2^4$$$.
  • ($$$30$$$ points): The sum of $$$2^K$$$ across all test cases does not exceed $$$2^6$$$.
  • ($$$60$$$ points): No additional constraints.
Example
Input
5
1
00
2
0101
2
0110
3
00011111
4
1111111111111111
Output
-1
2
0 1
1 0
-1
4
0 1 3 3
1 0 2 3
3 2 0 1
3 3 1 0
1
0
Note

In the first test case, it can be shown that it is impossible to construct the desired maze.

In the second test case, a possible construction is a maze with $$$2$$$ sites connected by a tunnel using key $$$1$$$.

  • With keys $$$S = \varnothing$$$ corresponding to $$$x_0 = \texttt{0}$$$, it is impossible to traverse the entire maze.
  • With keys $$$S = \{1\}$$$ corresponding to $$$x_1 = \texttt{1}$$$, it is possible to traverse the entire maze.
  • With keys $$$S = \{2\}$$$ corresponding to $$$x_2 = \texttt{0}$$$, it is impossible to traverse the entire maze.
  • With keys $$$S = \{1, 2\}$$$ corresponding to $$$x_3 = \texttt{1}$$$, it is possible to traverse the entire maze.

In the third test case, it can be shown that it is impossible to construct the desired maze.

In the fourth test case, a possible construction is the following maze with $$$4$$$ sites:

In the fifth test case, a possible construction is a maze with only $$$1$$$ site. With any set of keys, it is possible to traverse the entire maze.