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:
/*
    JAI MATA DI
 */

import java.util.*;
import java.util.concurrent.LinkedBlockingDeque;
import java.io.*;
import java.math.BigInteger;

public class Codechef {
	  static class FR{
			BufferedReader br;
			StringTokenizer st;
			public FR() {
				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; 
		    } 
		}
	 static int mod  = 1000000007;
	 static int gcd(int a, int b)
	  {      
	     if (b == 0)
	        return a;
	     return gcd(b, a % b); 
	  }
	 static long gcd(long a, long b)
	  {      
	     if (b == 0)
	        return a;
	     return gcd(b, a % b); 
	  }
	 static boolean[] prime(int num) {
			boolean[] bool = new boolean[num];
		     
		      for (int i = 0; i< bool.length; i++) {
		         bool[i] = true;
		      }
		      for (int i = 2; i< Math.sqrt(num); i++) {
		         if(bool[i] == true) {
		            for(int j = (i*i); j<num; j = j+i) {
		               bool[j] = false;
		            }
		         }
		      }
		      if(num >= 0) {
		    	  bool[0] = false;
		    	  bool[1] = false;
		      }
		      
		      return bool;
		}
	 static class Pair implements Comparable<Pair>{
	 		int ind;
	 		int val;
	 		Pair(int key , int value){
	 			this.ind = key;
	 			this.val = value;
	 		}
			@Override
			public int compareTo(Pair o) {
				return this.val - o.val;
			}
//			@Override
//			public int hashCode(){
//				return first + second;
//			}
	 	}
	 	
	 
	 

/* ***************************************************************************************************************************************************/	 
	 	 
	 public static void main(String args[]) {

		 FR sc = new FR();
		 int tc = sc.nextInt();
		 StringBuilder sb = new StringBuilder();
		 
		 while(tc-->0) {
			 int n = sc.nextInt();
			 if(n==1) {
				 sb.append("1\n");
				 continue;
			 }
			 int[][] arr = new int[n][n];
			 int num = 1;
			 for(int k = 0 ; k<n ; k++ ) {
				 for(int i = 0 ; i < n ; i ++) {
					 int j = i + k;
					 if(j<n && i<n) arr[i][j] = num++;
				 }
			 }
			 for(int k = 1 ; k<n ; k++) {
				 for(int i = 0 ; i<n ; i++) {
					 int j = i - k;
					 if(j>=0 && i>=0) arr[i][j] = num++;
				 }
			 }
			 int temp = arr[0][n-1];
			 arr[0][n-1] = arr[n-1][1];
			 arr[n-1][1] = temp;
//			 
//			 temp = arr[0][0];
//			 arr[0][0] = arr[n-1][0];
//			 arr[n-1][0] = temp;
			 boolean cond = true;
			 for(int i = 0 ; i<n ; i++) {
				 for(int j = 0 ; j<n ;j++) {
					 if(j+1 < n && Math.abs(arr[i][j] - arr[i][j+1])==1) {
						 cond = false; break;
					 }
					 if(j-1 >= 0 && Math.abs(arr[i][j] - arr[i][j-1])==1) {
						 cond = false; break;
					 }
					 if(i+1 < n && Math.abs(arr[i][j] - arr[i+1][j])==1) {
						 cond = false; break;
					 }
					 if(i-1 >= 0 && Math.abs(arr[i][j] - arr[i-1][j])==1) {
						 cond = false; break;
					 }
				 }
			 }
			 if(!cond) sb.append("-1\n");
			 else{
				 for(int i = 0 ; i<n ; i++) {
					 for(int j = 0 ;j<n ; j++) {
						 sb.append(arr[i][j]+" ");
					 }sb.append("\n");
				 }
			 }
			 
			 
			 
			 
		 }
	
	System.out.println(sb);
	
	 }

	
	
}