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:

0	1
2	3

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

0

values:$$$[0]$$$ — MEX: $$$1$$$

0

1

values:$$$[0, 1]$$$ — MEX: $$$2$$$

0

2

values:$$$[0, 2]$$$ — MEX: $$$1$$$

0	1
2	3

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.

Idx	Name	Rating
A	Mex in the Grid	1300
B	Quartet Swapping	1800
C	23 Kingdom	2200
D	Mani and Segments	2500
E	Kia Bakes a Cake	3100
F	Shoo Shatters the Sunshine	3300

Codeforces Round 1024 (Div. 1)