L. No Arithmetic subsequence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Construct an $$$n \times n$$$ grid with numbers from $$$1$$$ to $$$n \times n$$$ (each number exists exactly once) such that there is no row nor column that contains a subsequence (has exactly more than $$$2$$$ elements) which forms an Arithmetic Progression.

Arithmetic Progression is a sequence of numbers in order, in which the difference between any two consecutive numbers is a constant value.

Input

The first line of input contains a single integer $$$T$$$, the number of test cases.

The next $$$T$$$ lines each contains a single integer $$$n$$$ $$$(3 \le n \le 500)$$$, the dimension of the grid.

The sum of $$$n$$$ over all test cases doesn't exceed $$$500$$$

Output

For each test case with input $$$n$$$ print n lines each having n integers describing the required grid. It is guaranteed that there is always one solution at least. If there are multiple answers print any of them.

Example
Input
1
3
Output
1 3 2 
7 9 8 
4 6 5