$T$ 個のテストケースについて、以下の問題を解いてください。ただし、この問題はすべてのテストケースに正解したうえで、後に示す「追加の条件」を満たす場合のみ正答と判定されます。

問題

正整数 $N$ が与えられます。以下の条件を満たす $5$ 行 $500$ 列のグリッドを $1$ つ出力してください。本問題の制約下でそのようなグリッドは必ず存在します。

条件

• $1$ つのスタート地点、$1$ つのゴール地点、空きマス、壁からなる。
• スタート地点から上下左右に隣接する空きマスに移動することを繰り返してゴール地点に至る経路が存在し、そのうち移動回数が最も少ないものの個数がちょうど $N$ である。

各マスの状態は以下の $4$ 種類の文字で表すこととします。

• S：スタート地点かつ空きマス。
• G：ゴール地点かつ空きマス。
• .：空きマス。
• #：壁。

追加の条件

$\mathrm{diff}(A,B)$ をグリッド $A$ と $B$ の相異なるマスの数とする。厳密には、$A_{i,j}$ を グリッド $A$ の $i$ 行 $j$ 列として

$\mathrm{diff}(A,B) = |\lbrace{(i,j)\mid A_{i,j} \neq B_{i,j}\rbrace}|$

と定める。

$t$ 番目のテストケースに対する出力を $A^{(t)}$ として、$\sum_{t=1}^{T-1} \mathrm{diff}(A^{(t)},A^{(t+1)}) \le 3000$ を満たす。

• 入力はすべて整数
• $1 \le T \le 500$
• $1 \le N \le 4\times 10^{6}$

この問題には、部分点が設定されている。部分点の採点方法については、コンテストトップ を参照すること。

1. ($200$ 点)

• $N \leq 5 \times 10^4$

2. ($300$ 点)

• $N \leq 2.5 \times 10^5$

3. ($200$ 点)

• 追加の制約はない。

入力は標準入力から与えられる。入力の $1$ 行目は以下の形式である。

その後、$T$ 個のテストケースが続く。各テストケースは以下の形式で与えられる。

$5T$ 行出力せよ。$5(t-1)+1$ 行目から $5t$ 行目には $t$ 番目のテストケースの答えを出力せよ。
テストケースごとに余計な改行を入れるなどしてはならない。