You are given $n^2$ cards with values from $0$ to $n^2-1$. You are to arrange them in a $n$ by $n$ grid such that there is exactly one card in each cell.

The MEX (minimum excluded value) of a subgrid$^{\text{∗}}$ is defined as the smallest non-negative integer that does not appear in the subgrid.

Your task is to arrange the cards such that the sum of MEX values over all $\left(\frac{n(n+1)}{2}\right)^2$ subgrids is maximized.

$^{\text{∗}}$A subgrid of a $n$ by $n$ grid is specified by four numbers $l_1, r_1, l_2, r_2$ satisfying $1\le l_1\le r_1\le n$ and $1\le l_2\le r_2\le n$. The element in the $i$-th row and the $j$-th column of the grid is part of the subgrid if and only if $l_1\le i\le r_1$ and $l_2\le j\le r_2$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1\le n\le 500$) — the side length of the grid.

It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.

Output

For each test case, output $n$ lines, each containing $n$ integers representing the elements of the grid.

If there are multiple answers, you can output any of them.

Note

In the first test case, one valid arrangement is:

0123

There are $9$ subgrids in total, and the $4$ of them with non-zero MEX are shown below:

0 values:$[0]$ — MEX: *$1$01 values:$[0, 1]$ * — MEX: *$2$02 values:$[0, 2]$ * — MEX: *$1$0123 values:$[0, 1, 2, 3]$ * — MEX: $4$

The sum of MEX over all subgrids would be $1+2+1+4 = 8$. It can be proven that no other arrangements have a larger sum of MEX values.