Rhodoks 有一颗有 $$$n$$$ 个顶点的树,但他不记得它的结构。顶点索引从 $$$1$$$ 到 $$$n$$$。
如果索引为 $$$l$$$, $$$l + 1$$$, ..., $$$r$$$ 的顶点在 Rhodoks 树中形成连通分量,则线段 $$$[l,r]$$$ ($$$1 \leq l \leq r \leq n$$$) 是好的。否则就不好了。
例如,如果树是图中的树,则只有 $$$[3,4]$$$ 段是坏的,而所有其他段都是好的。
对于每个 $$$\frac{n(n+1)}{2}$$$ 段,Rhodoks 都会记住它是好是坏。你能帮他找回那棵树吗?如果有多个解决方案,请打印其中一个。
保证至少有一棵树满足Rhodoks的描述。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 1000$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2000$$$) — 树中的顶点数。
然后是 $$$n$$$ 行。这些行的第 $$$i$$$ 包含长度为 $$$n+1-i$$$ 的字符串 $$$n+1-i$$$,由 0 和 1 组成。如果段 $$$[i,i+j-1]$$$ 是好的,则 $$$good_i$$$ 的第 $$$j$$$ 字符为 1,否则 $$$good_i$$$ 的第 $$$j$$$ 字符为 0。
保证至少有一棵树与给定数据一致。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$。
输出
对于每个测试用例,打印描述您恢复的树的 $$$n-1$$$ 行。
第 $$$i$$$ 行应包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \leq u_i,v_i \leq n$$$),表示顶点 $$$u_i$$$ 和 $$$v_i$$$ 之间的边。
如果有多个解决方案,请打印其中一个。
示例
输入 #1
3 4 1111 111 10 1 6 111111 11111 1111 111 11 1 12 100100000001 11100000001 1000000000 100000000 10010001 1110000 100000 10000 1001 111 10 1
输出 #1
1 2 2 3 2 4 1 2 2 3 3 4 4 5 5 6 2 3 6 7 10 11 2 4 6 8 10 12 1 4 5 8 9 12 5 12 2 12
注意
第一个测试用例在语句中进行了解释。
在第二个测试用例中,一种可能的树如下:
在第三个测试用例中,一种可能的树如下: