Generate Pascal's Triangle

Given a positive integer n, generate the first n rows of Pascal's Triangle.

Each entry in the triangle is computed using the formula: $$ \binom{n}{k} = \frac{n!}{k!(n-k)!} $$, where the values outside the boundaries of the triangle are considered to be 0.

The first row is always 1. For each subsequent row, every number is the sum of the two numbers directly above it. Your task is to print the triangle for multiple test cases.

inputFormat

The input is read from stdin and has the following format:

T
n1
n2
...
nT

Where:

• T is an integer representing the number of test cases.
• Each of the next T lines contains an integer ni indicating the number of rows to generate for that test case.

outputFormat

For each test case, output the first n rows of Pascal's Triangle on stdout. Each row should be printed on a separate line with elements separated by a space. Separate the output of different test cases with a blank line.

## sample

1
1

1

</p>