打印貌似杨辉三角

给定层数n, 按照这样的格式打印前n行:

1

2 2

3 4 3

4 7 7 4

5 11 14 11 5

……

Input

一个正整数n(1<=n<=30), 表示需要打印多少行.

Output

按照上述格式打印类杨辉三角的前n行, 注意每行的末尾不要打印多余的空格.

Examples

Input

3

Output

1
2 2
3 4 3

来源

lema
Time limit 1 second
Memory limit 128 MB
讨论 统计