Not Adjacent Matrix
Description
We will consider the numbers $a$ and $b$ as adjacent if they differ by exactly one, that is, $|a-b|=1$.
We will consider cells of a square matrix $n \times n$ as adjacent if they have a common side, that is, for cell $(r, c)$ cells $(r, c-1)$, $(r, c+1)$, $(r-1, c)$ and $(r+1, c)$ are adjacent to it.
For a given number $n$, construct a square matrix $n \times n$ such that:
- Each integer from $1$ to $n^2$ occurs in this matrix exactly once;
- If $(r_1, c_1)$ and $(r_2, c_2)$ are adjacent cells, then the numbers written in them must not be adjacent.
The first line contains one integer $t$ ($1 \le t \le 100$). Then $t$ test cases follow.
Each test case is characterized by one integer $n$ ($1 \le n \le 100$).
For each test case, output:
- -1, if the required matrix does not exist;
- the required matrix, otherwise (any such matrix if many of them exist).
The matrix should be outputted as $n$ lines, where each line contains $n$ integers.
Input
The first line contains one integer $t$ ($1 \le t \le 100$). Then $t$ test cases follow.
Each test case is characterized by one integer $n$ ($1 \le n \le 100$).
Output
For each test case, output:
- -1, if the required matrix does not exist;
- the required matrix, otherwise (any such matrix if many of them exist).
The matrix should be outputted as $n$ lines, where each line contains $n$ integers.
Samples
3
1
2
3
1
-1
2 9 7
4 6 3
1 8 5