Busy Beaver 正在设计一个密室！他目前的设计是一个包含 $N$ 个不同地点的迷宫，其中任意两个地点之间都由一条双向隧道直接相连，总共有 $\frac{N(N-1)}{2}$ 条隧道。

为了让迷宫更有趣，每条隧道都由 $K$ ($1 \le K \le 10$) 把钥匙中的一把锁住，钥匙编号为 $1, 2, \dots, K$。只有当拥有隧道对应的钥匙 $a_{ij}$ 时，才能在地点 $i$ 和 $j$ 之间通行。

此外，Busy Beaver 希望设计这个迷宫，使得只有特定的钥匙集合才能让你走遍整个迷宫。具体来说，对于每个子集 $S \subseteq \{1, 2, \dots, K\}$，都有一个 $x_S \in \{0, 1\}$，满足：

• 如果 $x_S = 1$，则仅使用 $S$ 中的钥匙，可以在迷宫中的任意两个地点之间移动。
• 如果 $x_S = 0$，则存在某一对地点，仅使用 $S$ 中的钥匙无法互相到达。

请判断该任务是否可行。如果可行，请提供任何一种至多包含 $300$ 个地点的有效构造。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $T$ ($1 \le T \le 300$)。接下来是各测试用例的描述。

每个测试用例的第一行包含整数 $K$ ($1 \le K \le 10$)，即钥匙的数量。

每个测试用例的第二行包含一个字符串 $x$ ($|x| = 2^K, x_i \in \{0, 1\}$)，使得对于每个 $S$，若 $i = \sum_{t \in S} 2^{t-1}$，则 $x_S := x_i$。注意字符串 $x$ 是从 $0$ 开始索引的，即 $0 \le i < 2^K$。

保证所有测试用例中 $2^K$ 的总和不超过 $2^{10}$。

输出格式

对于每个测试用例，如果满足给定的约束条件是可能的，则输出的第一行应包含一个整数 $N$ ($1 \le N \le 300$)，即地点的数量。接下来的 $N$ 行，每行应包含 $N$ 个整数 $a_{ij}$ ($a_{ii} = 0, a_{ij} = a_{ji}, 1 \le a_{ij} \le K$ 当 $i \neq j$ 时)，其中当 $i \neq j$ 时，地点 $i$ 和 $j$ 之间的隧道使用钥匙 $a_{ij}$。

如果有多种解，输出其中任意一种即可。否则，如果无解，则输出单个整数 $-1$。

由于评测限制，所有输出中 $N^2$ 的总和不应超过 $2 \cdot 10^5$。可以证明这足以解决该问题。

子任务

如果你能正确判断是否存在解，但构造不正确，你将获得每个子任务 20% 的分数。具体来说，为了获得这些分数，当不存在解时，你必须输出 $-1$。当存在解时，你必须输出某个 $N$ ($1 \le N \le 300$) 以及一个满足规格 ($a_{ii} = 0, a_{ij} = a_{ji}, 1 \le a_{ij} \le K$ 当 $i \neq j$ 时) 的矩阵 $a$。

本题共有三个子任务：

• (10 分)：所有测试用例中 $2^K$ 的总和不超过 $2^4$。
• (30 分)：所有测试用例中 $2^K$ 的总和不超过 $2^6$。
• (60 分)：无附加限制。

样例

输入 1

5
1
00
2
0101
2
0110
3
00011111
4
1111111111111111

输出 1

-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

说明

在第一个测试用例中，可以证明无法构造出所需的迷宫。

在第二个测试用例中，一种可能的构造是一个包含 2 个地点的迷宫，它们之间由使用钥匙 1 的隧道连接。

• 对于钥匙集合 $S = \emptyset$（对应 $x_0 = 0$），无法走遍整个迷宫。
• 对于钥匙集合 $S = \{1\}$（对应 $x_1 = 1$），可以走遍整个迷宫。
• 对于钥匙集合 $S = \{2\}$（对应 $x_2 = 0$），无法走遍整个迷宫。
• 对于钥匙集合 $S = \{1, 2\}$（对应 $x_3 = 1$），可以走遍整个迷宫。

在第三个测试用例中，可以证明无法构造出所需的迷宫。

在第四个测试用例中，一种可能的构造是以下包含 4 个地点的迷宫：

在第五个测试用例中，一种可能的构造是一个仅包含 1 个地点的迷宫。对于任何钥匙集合，都可以走遍整个迷宫。