The triangle below is known as Pascal’s triangle.

In this triangle, the value at a position is equal to the sum of values of the 2 elements just above it.

Examples

• The 2^nd element of 5^th row is 1+3 => 4
• The 3^rd element of 5^th row is 3+3 => 6
• The 4^th element of 5^th row is 3+1 => 4

For the leftmost and the rightmost position in each row, the value is 1. The element in the first row is also 1.

Given a number n, find the n^th row of pascal’s triangle.

Testing

Input Format

The first line contains ‘T’ denoting the no. of test cases.

Next T lines contains a number 'n' denoting the row number of pascal’s triangle.

Output Format

For each test case, a line containing ‘n’ space-separated integers denoting the elements in the n^th row.

Examples

Sample Input

3
4
5
6

Expected Output

1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

Constraints

1 <= T <= 100

1 <= n <= 30