在三角形网格阵列中，每边有 $N$ 个单元格，一个“皇后”棋子可以攻击任何与包含该棋子的单元格所在的边平行的直线上的单元格。例如，在图 1 的阵列中，位于黑色单元格上的皇后可以攻击所有阴影单元格。边长为 $N$ 的三角形 $N$ 皇后问题，旨在寻找一个三角形阵列中皇后位置的极大集合，使得没有任何皇后可以攻击到其他任何皇后。例如，图 2 中的黑色单元格给出了一个边长为 6 的阵列中皇后位置的极大集合。事实证明，边长为 $N$ 的阵列中，非攻击皇后位置的极大数量总是 $\lfloor(2N + 1)/3\rfloor$。

编写一个程序，给定三角形阵列的边长 $N$，找出该阵列中非攻击皇后位置的一个极大集合（数量为 $\lfloor(2N + 1)/3\rfloor$ 个）。

输入格式

输入的第一行包含一个整数，指定随后的数据集数量 $C$ ($1 \le C \le 1000$)。每个数据集由一行组成，包含一个整数 $N$ ($1 \le N \le 1000$)，即三角形阵列的边长。

输出格式

对于每个问题，第一行输出问题编号（从 1 开始）、一个空格、输入的大小 $N$、一个空格以及皇后位置的数量。接下来的行输出皇后位置，每行输出 8 个位置，最后一行除外。每个位置的格式为：左括号（‘[’）、从 1 开始的行号、逗号、从 1 开始的行内从左侧起的位置、右括号（‘]’）。同一行内的位置由单个空格分隔。例如，图 2 中的皇后位置为 [1,1] [4,2] [5,4] [6,3]。位置值输出行之后应紧跟一个空行。

图 1

图 2

样例

样例输入 1

6
3
6
9
10
14
18

样例输出 1

1 3 2
[1,1] [3,2]

2 6 4
[3,1] [4,3] [5,5] [6,2]

3 9 6
[4,1] [5,3] [6,5] [7,7] [8,2] [9,4]

4 10 7
[4,1] [5,3] [6,5] [7,7] [8,2] [9,4] [10,6]

5 14 9
[6,1] [7,3] [8,5] [9,7] [10,9] [11,11] [12,2] [13,4]
[14,6]

6 18 12
[7,1] [8,3] [9,5] [10,7] [11,9] [12,11] [13,13] [14,2]
[15,4] [16,6] [17,8] [18,10]

说明

1. 对于特定问题，可能存在许多不同的正确答案，因此你的答案不必与上述样例输出相同。
2. 针对此问题的一些解法可能会导致超时。在提交你的解决方案之前，请务必测试较大的数值。