Given a positive integer n, print the first n rows of Pascal's triangle with leading spaces to form a triangle shape.

Input

• One positive integer n.

Output

• Numbers on the same line are separated by exactly one space. Use leading spaces for alignment.

Constraints

• 1 <= n <= 20

Example

Input

5

Output

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