Loay has won first two contests in AAST training level 3, and he is wondering: Will his competitors fight back hard in next contests? Let's hope they do. While he was thinking, he was drawing a special square.

This special square has unique properties, its sides has length 3^n (i.e. if n is 2, it is 9×9 square), and when it divided to 9 equal squares, the middle one is just empty square while the other 8 are special squares too (Isn't it interesting?, see sample input and output for more understanding).

NOTE: 1×1 square filled with '0' is also special square.

Input

just one integer N (1<=N<=7)

Output

print the given special square whose sides of length 3^N

Example

Input:
1

Output:
000
0 0
000

Input:
2

Output:
000000000
0 00 00 0
000000000
000   000
0 0   0 0
000   000
000000000
0 00 00 0
000000000

Input:
3

Output:
000000000000000000000000000
0 00 00 00 00 00 00 00 00 0
000000000000000000000000000
000   000000   000000   000
0 0   0 00 0   0 00 0   0 0
000   000000   000000   000
000000000000000000000000000
0 00 00 00 00 00 00 00 00 0
000000000000000000000000000
000000000         000000000
0 00 00 0         0 00 00 0
000000000         000000000
000   000         000   000
0 0   0 0         0 0   0 0
000   000         000   000
000000000         000000000
0 00 00 0         0 00 00 0
000000000         000000000
000000000000000000000000000
0 00 00 00 00 00 00 00 00 0
000000000000000000000000000
000   000000   000000   000
0 0   0 00 0   0 00 0   0 0
000   000000   000000   000
000000000000000000000000000
0 00 00 00 00 00 00 00 00 0
000000000000000000000000000