AZY and Pascal's Triangle

Warning

This question requires a level of English reading skills and Please use queue. So make sure you have the ability to pass CET-4 and you can implement a queue ADT in C/C++.

by Yours sincerely, AZY

Description

Please print Pascal's Triangle, which is believed first studied by Chinese.

In mathematics, Pascal's triangle is a triangular array of the binomial coefficients. Each number is the sum of the two directly above it.

In order to simplify the question, the quantity of input AZY's data is very small. So take it eaaaaasy~

Input

The input file consists of several sets of data, each set is just a positive whole number, n(0<n<=100).

Output

For each "n", please print the whole Pascal's Triangle of n rows.

Be cautious to control output format, and do not forget to add an empty line after each set of output is finished.

Sample Input

5

Sample output

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

Attention:

In sample output,

Number of spaces before the 1st "1" in the 1st row is 19.

Number of spaces before the 1st "1" in the 2nd row is 15.

Number of spaces before the 1st "1" in the 3rd row is 11.

Number of spaces before the 1st "1" in the 4th row is 7.

Number of spaces before the 1st "1" in the 5th row is 3.

Tips:

You can make each number of the triangle takes 4 spaces width and the next number should appear after 4 spaces.