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:
#####  HAR HAR MAHADEV  ||  JAI SHREE RAM  #####
###  @created by SHATMANYU GUPTA(shatmanyu_04)  ###
mod=pow(10,9)+7;MOD=998244353
## PE -> end=" " ##
from sys import stdin,stdout ; from heapq import heapify,heappush,heappop;from bisect import bisect,bisect_left,bisect_right ; from math import *
from itertools import * ; from collections import *
sml={chr(ord("a")+i):i for i in range(26)};cap={chr(ord("A")+i):i for i in range(26)}
def get_list():return list(map(int,input().split()))
def get_int():return int(input())
def get_ints():return map(int,input().split())
def godprime(n):
    for i in range(2,int(sqrt(n))+1):
        if n%i==0:
            return False
def godpower(b,p):
    res=1
    while p>0:
        if p%2==0:
            b=b*b
            p//=2
        else:
            res*=b
            p-=1
    return res
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x
def get(n):
    d = []
    while n > 0:
        n1 = n%10
        d.append(n1)
        n//=10
    #d.reverse()
    return len(d)


for tt in range(get_int()):
    n = get_int()
    e = [];o =[]
    for i in range(1,n*n+1):
        if i%2:
            o.append(i)
        else:
            e.append(i)
    ans = e + o
    mat = [[0 for i in range(n)]for i in range(n)]
    for i in range(n):
        for j in range(n):
            mat[i][j] = ans.pop(0)
    if n == 2:
        print(-1)
    else:
        for i in mat:
            print(*i)














##def dfs_path(v,strt,end,n):
##    def printPath(stack):
##        return len(stack)-1
##    def DFS(fg,vis, x, y, stack):
##        stack.append(x)
##        if (x == y):
##            ans = printPath(stack)
##            fg = 1
##        vis[x] = True
##        if (len(v[x]) > 0):
##            for j in v[x]:
##                if (vis[j] == False):
##                    DFS(fg,vis, j, y, stack)
##        if fg == 1:
##            return ans
##                                
##        del stack[-1]
##        print("ddd")
##    def DFSCall(x, y, n, stack):
##        vis = [0]*(n+1)
##        fg = 0
##        ans2 = DFS(fg,vis, x, y, stack)
##        print("terminate",ans2)
##    ans1 = DFSCall(strt,end,n,[])
##    return ans1
##        

    
##for tt in range(get_int()):
##    n,k,a = get_ints()
##    s = get_list()
##    adj = {i:[] for i in range(1,n+1)}
##    for i in range(n-1):
##        u,v = get_ints()
##        adj[u].append(v)
##        adj[v].append(u)
##    d = {i:[] for i in range(1,n+1)}
##    for i in range(1,n+1):
##        for j in s:
##            d[i].append(dfs_path(adj,i,j,n))
##    print(d)
##    
##    
##def merge(l,strt,mid,end):
##    ans = 0;i = strt;j = mid + 1
##    while i < mid+1 and j < end:
##        if l[i] < l[j]:
##            j += 1
##            ans += 1
##        
##        
##def mergesort(l,strt,end,c):
##    if strt < end:
##        mid = (strt + end)//2
##        mergesort(l,strt,mid,c)
##        mergesort(l,mid+1,end,c)
##        c += merge(l,strt,mid,end)
##    return c
##
##for tt in range(get_ints()):
##    n = get_int()
##    l = get_list()