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 JAVA):

Solution:

import java.util.*;
import java.io.*;
import java.math.BigInteger;
public class Main {
	//  Solution 
   public static void main(String args[])
	{int t=in.nextInt();
	while(t-->0) {
		int n=in.nextInt();
		if(n==2)
		out.append(-1+"\n");
		else {
			int val=1;
			for(int i=0;i<n;i++) {
				for (int j = 0; j < n; j++) {
					out.append(val+" ");
					val+=2;
					if(val>n*n)
						val=2;
				}
			out.append("\n");}
		}
			
	}
	out.close();
}

static void sort(int[] a) {
	ArrayList<Integer> l=new ArrayList<>();
	for (int i:a) l.add(i);
	Collections.sort(l);
	for (int i=0; i<a.length; i++) a[i]=l.get(i);
}
   static boolean is_prime(int n) {
	   
	   if(n%2==0)
		   return false;
	   for (int i = 3; i * i<= n; i+=2) {
		if(n%i==0)
			return false;
	}
	   
	   return true;
   }
    static long mod=1000000007L;
    static long gcd(long a,long b) {
    	if(a==0)
    		return b;
    	return gcd(b%a,a);
    }
    static long dp[][][];
   
    static Reader in=new Reader();
    public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static class Reader 
    { 
        private InputStream mIs;private byte[] buf = new byte[1024];private int curChar,numChars;public Reader() { this(System.in); }public Reader(InputStream is) { mIs = is;} 
        public int read() {if (numChars == -1) throw new InputMismatchException();if (curChar >= numChars) {curChar = 0;try { numChars = mIs.read(buf);} catch (IOException e) { throw new InputMismatchException();}if (numChars <= 0) return -1; }return buf[curChar++];} 
        public String nextLine(){int c = read();while (isSpaceChar(c)) c = read();StringBuilder res = new StringBuilder();do {res.appendCodePoint(c);c = read();}while (!isEndOfLine(c));return res.toString() ;} 
        public String s(){int c = read();while (isSpaceChar(c)) c = read();StringBuilder res = new StringBuilder();do {res.appendCodePoint(c);c = read();}while (!isSpaceChar(c));return res.toString();} 
        public long l(){int c = read();while (isSpaceChar(c)) c = read();int sgn = 1;if (c == '-') { sgn = -1 ; c = read() ; }long res = 0; do{ if (c < '0' || c > '9') throw new InputMismatchException();res *= 10 ; res += c - '0' ; c = read();}while(!isSpaceChar(c));return res * sgn;} 
        public int nextInt(){int c = read() ;while (isSpaceChar(c)) c = read();int sgn = 1;if (c == '-') { sgn = -1 ; c = read() ; }int res = 0;do{if (c < '0' || c > '9') throw new InputMismatchException();res *= 10 ; res += c - '0' ; c = read() ;}while(!isSpaceChar(c));return res * sgn;} 
        public double d() throws IOException {return Double.parseDouble(s()) ;}
        public boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } 
        public boolean isEndOfLine(int c) { return c == '\n' || c == '\r' || c == -1; } 
        public int[] arr(int n){int[] ret = new int[n];for (int i = 0; i < n; i++) {ret[i] = nextInt();}return ret;}
    }
}
class node implements Comparable<node> {
int val,pos;
node(int val,int pos){
	this.pos=pos;this.val=val;
}
@Override
public int compareTo(node o) {
	
	return val-o.val;
}
 
 
}
class xtree{
	public xtree(int n,int a[]) {
		this.a=a;
		seg=new int[n*4];
		//lazy=new int[n*4];
		build(1,0,n-1);
	}
	int seg[], a[],lazy[];
	    void check(int p,int s,int e) {
	        if(lazy[p]!=0) {
	            seg[p] += lazy[p];
	            if(s!=e) {
	                lazy[2*p] += lazy[p];
	                lazy[2*p+1] += lazy[p];
	            }
	            lazy[p] = 0;
	        }
	    }
	    
	     void build(int p,int s,int e) {
	        //check(p,s,e);
	        
	        if(s==e) {
	            seg[p] = a[s];
	            return;
	        }
	        
	        build(2*p,s,(s+e)/2);
	        build(2*p+1,(s+e)/2+1,e);
	        
	        seg[p] = seg[2*p]+ seg[2*p+1];
	    }
	    
	   void update(int p,int s,int e,int i,int v) {
	       // check(p,s,e);
	        
	        if(s==e) {
	            seg[p] = v;
	            return;
	        }
	        
	        if(i<=(s+e)/2) update(2*p,s,(s+e)/2,i,v);
	        else update(2*p+1,(s+e)/2+1,e,i,v);
	        
	        seg[p] = seg[2*p]+seg[2*p+1];
	    }
	    
	     void update(int p,int s,int e,int a,int b,int v) {
	        //check(p,s,e);
	        
	        if(s>=a && e<=b) {
	            seg[p] += v;
	            
	            if(s!=e) {
	                lazy[2*p] += v;
	                lazy[2*p+1] += v;
	            }
	            
	            return;
	        }
	        
	        if(s>b || e<a)
	            return;
	        
	        update(2*p,s,(s+e)/2,a,b,v);
	        update(2*p+1,(s+e)/2+1,e,a,b,v);
	        
	        seg[p] = seg[2*p]+seg[2*p+1];
	    }
    
 
    
    int get(int p,int s,int e,int a,int b) {
        if(s>=a && e<=b)
            return seg[p];
        
        if(s>b || e<a)
            return 0; 
        
        return get(2*p,s,(s+e)/2,a,b)+ get(2*p+1,(s+e)/2+1,e,a,b);
    }
}
 
class FastReader
    {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader()
        {
            br = new BufferedReader(new
                     InputStreamReader(System.in));
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt()
        {
            return Integer.parseInt(next());
        }
 
        long nextLong()
        {
            return Long.parseLong(next());
        }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
}
 
class Sorting{
 
 public static long[] bucketSort(long[] array, int bucketCount) {
 
 if (bucketCount <= 0) throw new IllegalArgumentException("Invalid bucket count");
 
 if (array.length <= 1) return array; //trivially sorted
 
 
 
 long high = array[0];
 
 long low = array[0];
 
 for (int i = 1; i < array.length; i++) { //find the range of input elements
 
 if (array[i] > high) high = array[i];
 
 if (array[i] < low) low = array[i];
 
 }
 
 double interval = ((double)(high - low + 1))/bucketCount; //range of one bucket
 
 
 ArrayList<Long> buckets[] = new ArrayList[bucketCount];
 
 for (int i = 0; i < bucketCount; i++) { //initialize buckets
 
 buckets[i] = new ArrayList();
 
 }
 
 
 
 for (int i = 0; i < array.length; i++) { //partition the input array
 
 buckets[(int)((array[i] - low)/interval)].add(array[i]);
 
 }
 
 
 int pointer = 0;
 
 for (int i = 0; i < buckets.length; i++) {
 
 Collections.sort(buckets[i]); //mergeSort
 
 for (int j = 0; j < buckets[i].size(); j++) { //merge the buckets
 
 array[pointer] = buckets[i].get(j);
 
 pointer++;
 
 }
 
}
 
return array;
 
}
}
 class LongestCommonSubsequence 
{ 
  
  /* Returns length of LCS for X[0..m-1], Y[0..n-1] */
	 int lcs( char[] X, char[] Y, int m, int n ,int K) 
	  { 
		 int L[][] = new int[m+1][n+1]; 
		 int ans[][]=new int[m+1][n+1];
		 int min[][] = new int[m+1][n+1]; 
		 for(int i=0;i<=n;i++) 
			 for(int j=0;j<=m;j++) 
				 min[j][i]='z'+1;
	    /* Following steps build L[m+1][n+1] in bottom up fashion. Note 
	         that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
	    for (int i=0; i<=m; i++) 
	    { 
	      for (int j=0; j<=n; j++)
	      { 
	        if (i == 0 || j == 0) 
	            L[i][j] = 0; 
	        else if (X[i-1] == Y[j-1]) { 
	            L[i][j] = L[i-1][j-1] + 1; 
	            ans[i][j]=ans[i-1][j-1]+X[i-1];
	         
	        }
	        else {
	            L[i][j] = max(L[i-1][j], L[i][j-1]); }
	      } 
	    } 
	  return L[m][n]; 
	  } 
	  
	  /* Utility function to get max of 2 integers */
	  int max(int a, int b) 
	  { 
	    return (a > b)? a : b; 
	  } 
 
     // Returns length of LCS for X[0..m-1], Y[0..n-1] 
     static String lcs(String X, String Y, int m, int n) 
     { 
         int[][] L = new int[m+1][n+1]; 
    
         // Following steps build L[m+1][n+1] in bottom up fashion. Note 
         // that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1]  
         for (int i=0; i<=m; i++) 
         { 
             for (int j=0; j<=n; j++) 
             { 
                 if (i == 0 || j == 0) 
                     L[i][j] = 0; 
                 else if (X.charAt(i-1) == Y.charAt(j-1)) 
                     L[i][j] = L[i-1][j-1] + 1; 
                 else
                     L[i][j] = Math.max(L[i-1][j], L[i][j-1]); 
             } 
         } 
    
         // Following code is used to print LCS 
         int index = L[m][n]; 
         int temp = index; 
    
         // Create a character array to store the lcs string 
         char[] lcs = new char[index+1]; 
         lcs[index] = '\u0000'; // Set the terminating character 
    
         // Start from the right-most-bottom-most corner and 
         // one by one store characters in lcs[] 
         int i = m; 
         int j = n; 
         while (i > 0 && j > 0) 
         { 
             // If current character in X[] and Y are same, then 
             // current character is part of LCS 
             if (X.charAt(i-1) == Y.charAt(j-1)) 
             { 
                 // Put current character in result 
                 lcs[index-1] = X.charAt(i-1);  
                   
                 // reduce values of i, j and index 
                 i--;  
                 j--;  
                 index--;      
             } 
    
             // If not same, then find the larger of two and 
             // go in the direction of larger value 
             else if (L[i-1][j] > L[i][j-1]) 
                 i--; 
             else
                 j--; 
         } 
    
         // Print the lcs 
         StringBuilder Sd=new StringBuilder();
         for(int k=0;k<=temp;k++) 
             Sd.append(lcs[k]); 
      return Sd.toString();   
     }
 }