#P18186. Aim High

Aim High

Aim High

你将在二维平面上进行一个游戏。最初,对于每个满足 −100≤x≤100-100\le x\le100、−100≤y≤0-100\le y\le0 的整点 (x,y)(x,y),该点恰有一枚棋子;其他位置没有棋子。

你可以执行任意次以下操作,也可以不执行操作:

  • 选择两个相邻整点 (a,b)(a,b) 和 (c,d)(c,d),即 ∣a−c∣+∣b−d∣=1|a-c|+|b-d|=1。这两个点必须都至少有一枚棋子。
  • 将 (a,b)(a,b) 处的一枚棋子绕 (c,d)(c,d) 顺时针或逆时针旋转 90∘90^\circ,移动到相应位置,同时移除 (c,d)(c,d) 处的一枚棋子。

同一位置可以有多枚棋子。操作涉及的位置不必位于初始矩形内。

给定整数 NN,判断能否在所有操作结束后,使某个纵坐标至少为 NN 的位置存在至少一枚棋子。如果可以,输出任意一组合法操作。

共有 TT 组独立测试。每组测试都从上述初始局面重新开始。

输入格式

第一行一个整数 TT。

接下来 TT 行,每行一个整数 NN,表示一组测试。

输出格式

按照输入顺序输出每组测试的结果。

如果无法达到目标,输出一行 -1。

否则,先输出一行非负整数 KK,表示操作次数。接下来 KK 行,每行输出六个整数 ai,bi,ci,di,ei,fia_i,b_i,c_i,d_i,e_i,f_i,表示将 (ai,bi)(a_i,b_i) 处的一枚棋子绕 (ci,di)(c_i,d_i) 旋转 90∘90^\circ,移动到 (ei,fi)(e_i,f_i),并移除 (ci,di)(c_i,d_i) 处的一枚棋子。

你输出的每一步操作都必须合法,而且执行完全部操作后仍须满足目标。无需最小化操作次数。

每步恰好减少一枚棋子,而初始共有 2030120301 枚棋子,因此任何成功的合法方案自然满足 0≤K≤203000\le K\le20300;这不是额外限制。

数据范围

  • 1≤T≤61\le T\le6;
  • 每组测试中,1≤N≤61\le N\le6;
  • 所有输入均为整数。

样例

输入

1
1

输出

1
1 0 0 0 0 1

将 (1,0)(1,0) 处的棋子绕 (0,0)(0,0) 旋转至 (0,1)(0,1),同时移除 (0,0)(0,0) 处的一枚棋子,即可达到目标。两种旋转方向均可使用。