問題文

あなたはパズルゲームの開発をしており、「ちょうど良い」難易度のステージを作ろうとしています。

ステージは正方形グリッドで表され、通路、壁、スイッチの $3$ 種類のマスから構成されます。プレイヤーは通路マスまたはスイッチマスの上を移動することができますが、壁マスに立ち入ることはできません。

ステージを $N$ 行 $N$ 列のグリッドとし、上から $i$ 行目、左から $j$ 列目のマスを $(i, j)$ と表すとき、以下の全ての条件を満たすステージを作成することはできますか？ただし、ステージの大きさ $N$ は入力では与えられず、あなたが自由に定めることができます。

• $2 \leq N \leq 40$
• マス $(1, 1)$ 及び $(N, N)$ は通路マスである
• プレイヤーが右または下方向に隣り合うマスへの移動を繰り返してマス $(1, 1)$ から $(N, N)$ まで移動するとき、スイッチマスをちょうど $1$ 回だけ通る経路の数はちょうど $M$ 通りである

可能な場合はそのようなステージの一例を、不可能な場合は -1 を出力してください。

$T$ 個のテストケースが与えられるため、それぞれについて答えを出力してください。

制約

• 入力は全て整数
• $1 \leq T \leq 100$
• $1 \leq M \leq 10^{18}$

入力

入力は以下の形式で標準入力から与えられる。ここで、$case_i$ は $i$ 番目のケースを意味する。

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

各テストケースは以下の形式で与えられる。

$M$

出力

各ケースに対し、条件を満たすステージが存在しない場合は -1 を、条件を満たすステージが存在する場合は、以下の形式でその一例を出力してください。ただし、$S_i\ (1 \leq i \leq N)$ は長さ $N$ の文字列であり、$S_i$ の $j$ 文字目はステージの上から $i$ 行目、左から $j$ 列目のマスが通路マスの場合は .、壁マスの場合は #、スイッチマスの場合は P である必要があります。

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

各ケースに対する出力の最後に改行してください。

ビジュアライザ

出力結果のWeb版ビジュアライザがこちらで提供されています。

コンテスト中における、ビジュアライズ結果の共有や解法・考察に関する言及は禁止されています。ご注意下さい。

また、ビジュアライザの仕様に関する質問は原則受け付けません。あくまで補助ツールとしてご利用ください。

サンプル

サンプル1

入力

1
3

出力

5
..P..
.#..#
.##.#
.P#..
...P.

スイッチマスをちょうど $1$ 回だけ通る経路は $3$ 通りあります。