Pascal's Triangle

The Selby Science Centre has a bean machine in the foyer: a ball is dropped onto a peg, bounces left or right, lands on another peg, and so on down the board. The panel beside it explains why the balls pile up in the middle by showing, for each peg, how many different routes a ball could take to reach it. Those counts are exactly the rows of Pascal's triangle, and staff set the number of peg rows before each demonstration.

Task: Print the first n rows of Pascal's triangle.

Input

A single line holding one integer n, with 1 <= n <= 30.

Output

n lines. Row 1 holds one value, row 2 holds two, and so on, so row i holds i values separated by single spaces. No leading or trailing spaces on a line.

Example:

Input:
4

Output:
1
1 1
1 2 1
1 3 3 1