Print the first \(n\) rows of Pascal's triangle. Rows are indexed from \(0\) and each row begins and ends with \(1\).

Input

One line containing \(n\).

The input satisfies:

• \(1 \le n \le 50\)

Output

Print \(n\) rows. Values on a row are separated by single spaces.

Example

Input

1

Output

1