Construct a square matrix $a$ of size $n×n$ satisfying the following conditions,

Each row of the matrix is a permutation of size $n$

Each column of the matrix is a permutation of size $n$

The matrix is symmetric, that means $a[i][j] = a[j][i]$ for all possible $i,j$$(1≤i,j≤n)$

The matrix satisfies $a[i][i] = i$ for all $i$$(1≤i≤n)$

If it is possible to build such a matrix, print the matrix otherwise print $-1$.

Input

First line of input consists of a single integer $T$, the number of test cases $(1 ≤ T ≤ 5)$ Each test case consists of one line. First and only line of the test case contains $n$, the dimension of the matrix. $(1 ≤ n ≤ 1000)$.

Output

Print the matrix if possible, otherwise print $-1$. If there are multiple possible answers, anyone would be acceptable.

Sample

Input

Output

2
2
3

-1
1 3 2
3 2 1
2 1 3

We call a sequence of integers $A$ permutation if every integer from 1 to |A| appears exactly once in the sequence, where $|A|$ denotes the length of the sequence.