An element in Pascal's triangle can be defined recursively as follow:

~ \text{pascal(row, col)} = \begin{cases} 1&\text{, if col = 0 or row = col} \\ \text{pascal(row-1, col-1) + pascal(row-1, col)}&\text{, otherwise} \end{cases} ~

In this programming problem, your task is to print Pascal's triangle to the output stream. You need to define two functions: pascal and print_pascal, where pascal returns the Pascal's element of a given ~row~ and ~col~, and print_pascal outputs an ~n~-row Pascal's triangle.

Note that you should leave at least 3 characters of horizontal space for each element of Pascal's triangle. That is, you should use f'{e:3d}' or some other similar techniques to format each element.

For example, a 6-row Pascal's triangle is as follows (you don't need to output the ~row~ and ~col~ indices):

You can start with this template code and ensure your code can run correctly within this template:

def pascal(row, col):
    # your code here

def print_pascal(n):
    # your code here

# Note that the following code is for local testing purposes only. You should leave this part of code unchanged and not submit it to the OJ system.
T = int(input())
for t in range(T):
    n = int(input())
    print_pascal(n)

Please note that you only have to submit the definition of the pascal and print_pascal to the OJ system. The rest of the code is for your local testing purposes only.

Input Specification

The first line of the input gives the number of test cases, ~T~, and then ~T~ test cases follow.

For each test case, there will be a single line containing an integer ~n~ that indicates the number of rows in Pascal's triangle.

Constraints

~1 \leq T \leq 100~

~1 \leq n \leq 10~

Output Specification

For each test case, output an ~n~-row Pascal's triangle with at least 3 characters horizontal space for each element.

Sample Input

2
3
5

Sample Output

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

Hint

recursion for-loop formatted-output