Description

有一个奇幻的矩阵，在不停的变幻，其变幻方式为：

数字 0 变成矩阵

0 0

0 1

数字 1 变成矩阵

1 1

1 0

最初该矩阵只有一个元素 0，变幻 n 次后，矩阵会变成什么样？

例如，矩阵最初为：[0]；

矩阵变幻 1 次后：

0 0

0 1

矩阵变幻 2 次后：

0 0 0 0

0 1 0 1

0 0 1 1

0 1 1 0

Format

Input

一行一个不超过 10 的正整数 n。输出变幻 n 次后的矩阵。

Output

如题所示

Samples

2

0000
0101
0011
0110

3

00000000
01010101
00110011
01100110
00001111
01011010
00111100
01101001