E - Aim High Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

あなたは 2 次元平面を用いてゲームをします。始め、-100 \le x \le 100,-100 \le y \le 0 を満たす格子点 (x,y) に駒が 1 個ずつ置かれています。

あなたは以下の操作を 0 回以上行うことが出来ます。

  • 2 個の点の組 (a,b),(c,d) であって、|a-c|+|b-d| = 1 かつ (a,b),(c,d) 両方に駒が 1 個以上あるものを選ぶ。(a,b) にある駒 1 個を (c,d) を中心として時計回りか反時計周りに 90 度回転させた点に置き、(c,d) にある駒を 1 個消す。（既に移動先の点に駒が置かれていても良い。）

あなたの目標は操作が全て終わったときに y 座標が N 以上であるいずれかの点に駒が置かれている状態にすることです。目標が達成可能か判定し、可能ならば操作列を 1 個構築してください。

T 個のテストケースが与えられるので、それぞれについて解いてください。

制約

  • 1 \le T \le 6
  • 1 \le N \le 6

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

ここで、\mathrm{case}_i とは i 番目のテストケースを意味する。各テストケースは以下の形式で与えられる。

N

出力

T 個のテストケースへの出力を与えられた順に改行区切りで出力せよ。

それぞれのテストケースについては、目標を達成することが出来ないならば -1 を、そうでないならば操作回数を K、i 回目の操作で (a_i,b_i) にある駒を (c_i,d_i) を中心として (e_i,f_i) に移動させるとき以下のように出力せよ。

K
a_1 b_1 c_1 d_1 e_1 f_1
a_2 b_2 c_2 d_2 e_2 f_2
\vdots
a_K b_K c_K d_K e_K f_K

入力例 1

1
1

出力例 1

1
1 0 0 0 0 1

1 回目の操作で、(1,0) にある駒を (0,0) を中心に時計回りに 90 度回転させて (0,1) に置きます。

この操作によって y 座標が 1 以上である点 (0,1) に駒を置くことが出来たので、目標を達成できました。