有 $n$ 个人。他们之中每两个人要么是朋友，要么不是。朋友关系是双向的。

每个人都想选择自己的“挚友”——即他们朋友的一个非空子集。他们唯一需要满足的条件是，这 $n$ 个人的挚友集合必须两两不同。注意，“成为挚友”这一属性不一定是双向的（即，X 可能是 Y 的挚友，但 Y 不一定是 X 的挚友）。

给你所有的朋友关系。请找到一种选择挚友集合的方案，使得所有人的挚友集合大小之和最小。或者，如果无法找到满足条件的方案，请说明无解。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^4$) —— 测试用例的数量。接下来的行包含测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 500$) —— 人数。

接下来有 $n - 1$ 行，第 $i$ 行包含一个长度为 $n - i$ 且仅由字符 0 和 1 组成的字符串。对于每个 $j$ ($i < j \le n$)，如果 $i$ 和 $j$ 是朋友，则该字符串的第 $j - i$ 个字符为 1，否则为 0。

保证所有测试用例中 $n^2$ 的总和不超过 $2.5 \cdot 10^5$。

输出格式

按给定顺序输出每个测试用例的答案。

如果无法选择满足条件的挚友集合，输出一个整数 -1。

否则，输出 $n$ 行。第 $i$ 行应以 $s_i$ ($s_i \ge 1$) 开始 —— 为第 $i$ 个人选择的挚友数量。接着是该行中的 $s_i$ 个不同的整数 $a_{i,1}, \dots, a_{i,s_i}$ ($1 \le a_{i,j} \le n, a_{i,j} \ne i$) —— 第 $i$ 个人的挚友。对于每个 $j$ ($1 \le j \le s_i$)，人 $i$ 和 $a_{i,j}$ 必须是朋友。

所有集合 $\{a_{i,1}, \dots, a_{i,s_i}\}$ 必须两两不同。总和 $\sum_{i=1}^n s_i$ 应当尽可能小。

如果有多个可能的答案，你可以输出其中任意一个。

样例

输入样例 1

2
5
1000
011
10
1
3
11
0

输出样例 1

1 2
1 1
1 4
1 3
2 2 4
-1