Given a positive integer n, print the first n rows of Pascal's triangle.

Input

• One positive integer n.

Output

• Numbers on the same line are separated by exactly one space.

Constraints

• 1 <= n <= 20

Example

Input

5

Output

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1