D. Coprime
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$. Construct a $$$n \times n$$$ matrix $$$M$$$ that contains each integer from $$$1$$$ to $$$n^2$$$ exactly once. The $$$\gcd$$$ of all numbers in each row should be equal to $$$1$$$, and the $$$\gcd$$$ of all numbers in each column should be equal to $$$1$$$.

Formally, $$$M$$$ has to satisfy the following conditions:

  • $$$\gcd(M_{i,1},M_{i,2},\ldots,M_{i,n})=1$$$ for all $$$1 \le i \le n$$$.
  • $$$\gcd(M_{1,j},M_{2,j},\ldots,M_{n,j})=1$$$ for all $$$1 \le j \le n$$$.
Input

Each test contains multiple test cases. The first line of each test contains an integer $$$t$$$ ($$$1 \le t \le 200$$$) — the number of test cases.

The only line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 500$$$) — the size of $$$M$$$ to be constructed.

It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, if no possible $$$M$$$ exists, output $$$-1$$$.

Otherwise, output $$$n$$$ lines of $$$n$$$ integers each, where the $$$j$$$-th integer on the $$$i$$$-th line represents $$$M_{i,j}$$$.

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