Problem: 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 × 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 × 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. 

Input

The first line contains one integer t (1 ≤ t ≤ 100). Then t test cases follow.

Each test case is characterized by one integer n (1 ≤ n ≤ 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.

Example

Input


3
1
2
3


Output


1
-1
2 9 7
4 6 3
1 8 5

Solution (in PYTHON3):

Solution:
aa=[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 111, 222, 333, 444, 555, 666, 777, 888, 999, 1111, 2222, 3333, 4444, 5555, 6666, 7777, 8888, 9999, 11111, 22222, 33333, 44444, 55555, 66666, 77777, 88888, 99999, 111111, 222222, 333333, 444444, 555555, 666666, 777777, 888888, 999999, 1111111, 2222222, 3333333, 4444444, 5555555, 6666666, 7777777, 8888888, 9999999, 11111111, 22222222, 33333333, 44444444, 55555555, 66666666, 77777777, 88888888, 99999999, 111111111, 222222222, 333333333, 444444444, 555555555, 666666666, 777777777, 888888888, 999999999]
for _ in range(int(input())):
#     n,m=map(int,input().split())
    n=int(input())
    a=[]
    s=1
    for i in range(n):
        b=[]
        for j in range(n):
            b.append(s)
            s+=2
            if n%2==0 and s==n*n+1:
                s=2
            if n%2!=0 and s==n*n+2:
                s=2
        a.append(b)
    result=True
    if n==1:
        print(1)
    else:
        for i in range(n):
            for j in range(n):
                if i==0:
                    if j==0:
                        if abs(a[0][0]-a[0][1])==1 or abs(a[0][0]-a[1][0])==1:
                            result=False
                            break
                    elif j==n-1:
                        if abs(a[0][n-1]-a[0][n-2])==1 or abs(a[0][n-1]-a[1][n-1])==1:
                            result=False
                            break
                    else:
                        if abs(a[0][j]-a[0][j-1])==1 or abs(a[0][j]-a[0][j+1])==1 or abs(a[0][j]-a[1][j])==1:
                            result=False
                            break
                elif i==n-1:
                    if j==0:
                        if abs(a[n-1][0]-a[n-1][1])==1 or abs(a[n-1][0]-a[n-2][0])==1:
                            result=False
                            break
                    elif j==n-1:
                        if abs(a[n-1][n-1]-a[n-1][n-2])==1 or abs(a[n-1][n-1]-a[n-2][n-1])==1:
                            result=False
                            break
                    else:
                        if abs(a[n-1][j]-a[n-1][j-1])==1 or abs(a[n-1][j]-a[n-1][j+1])==1 or abs(a[n-1][j]-a[n-2][j])==1:
                            result=False
                            break
                else:
                    if j==0:
                        if abs(a[i][0]-a[i][1])==1 or abs(a[i][0]-a[i+1][0])==1 or abs(a[i][0]-a[i-1][0])==1:
                            result=False
                            break
                    elif j==n-1:
                        if abs(a[i][n-1]-a[i][n-2])==1 or abs(a[i][n-1]-a[i-1][n-1])==1 or abs(a[i][n-1]-a[i+1][n-1])==1:
                            result=False
                            break
                    else:
                        if abs(a[i][j]-a[i][j-1])==1 or abs(a[i][j]-a[i][j+1])==1 or abs(a[i][j]-a[i-1][j])==1 or abs(a[i][j]-a[i+1][j])==1:
                            result=False
                            break
    if result==False and n!=1:
        print(-1)
    elif result==True and n!=1:
        for i in a:
            print(*i,sep=' ')