Shortening codes

For given integer n, your task will be to print nth line of Pascal's triangle.

1 - 0th line

1 1 - 1st line

1 2 1 - 2nd line

1 3 3 1 - 3rd line

1 4 6 4 1 - 4th line

...

Input

The first line of the standard input contains one integer t (t<101) which is the number of test cases.

In each of the next t lines there is one integer n (0<=n<101).

Output

For each n, print nth line of Pascal's triangle.

Example

Input:
2
7
0
Output:
1 7 21 35 35 21 7 1
1