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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.stream.IntStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.math.BigInteger;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Dragons {
	 
    static class Pair {
        int a;
        int b;
        public Pair(int a, int b){
            this.a=a;
            this.b=b;
        }
    }
	static ArrayList<Integer>[]adjList;
	static boolean[] color;
	static boolean visited[];
	static int count =0;
	public static void main(String[] args) throws IOException {
        Scanner sc=new Scanner(System.in);
        int l=sc.nextInt();
        while(l>0) {
       int n=sc.nextInt();
      long arr[][]=new long[n][n];
//      for (long row[]:arr )
//    	    Arrays.fill(row, 0);
      
      long a=1;
    
      
      for(int i=0, j=0;i<n&&j<n;i++,j++) {
    	  arr[i][j]=a;
    	  a++;
      }
      for(int k=1;k<n;k++) {
      for(int i=0,j=k+i;i<n && j<n;i++,j++) {
    	  arr[i][j]=a;
    	  a++;
      }
      }
      for(int k=1;k<n;k++) {
          for(int i=0,j=k+i;i<n && j<n;i++,j++) {
        	  arr[j][i]=a;
        	  a++;
          }
          }
      long temp=arr[n-1][0];
      arr[n-1][0]=arr[0][n-1];
      arr[0][n-1]=temp;
      if(n==2) {
    	  System.out.println(-1);
      }else if(n==3){
    	  long tem=arr[0][1];
          arr[0][1]=arr[2][0];
          arr[2][0]=tem;
          
          for(int i=0;i<n;i++) {
        	  for(int j=0;j<n;j++) {
        		  System.out.print(arr[i][j]+" ");
        	  }
        	  System.out.println();
          }
      }else {
      for(int i=0;i<n;i++) {
    	  for(int j=0;j<n;j++) {
    		  System.out.print(arr[i][j]+" ");
    	  }
    	  System.out.println();
      }
      }
      l--;
        }
		}
	

	
	static int helper(int arr[],int v) {
		int prev=0;
		int curr=0;
		for(int i=1;i<=3000;i++) {
			 curr=v;
			if(prev>=v) {
				count+=curr;
				prev=arr[i];
			}else {
				count+=prev;
				curr-=prev;
				if(arr[i]>=curr) {
					count+=curr;
					prev=arr[i]-curr;
				}else {
					count+=arr[i];
					prev=0;
				}
				
		       
			}
			
			
			
			
		}
		 if(prev >= v){
	            count += v;
	        }
	        else{
	            count += prev;
	        }
	        return count;
		
		
		
	}
	  
		static int mod(int a, int m)
		{
		    return (a%m + m) % m;
		}
		
	static long getSum(long y)
    {
       long sum = 0;
 
        while (y != 0) {
            sum = sum + y % 10;
            y = y / 10;
        }
 
        return sum;
    }
	static boolean detect(int arr[],int x) {
		long sum=0;
		for(int i=0;i<arr.length;i++) {
			sum+=arr[i];
			if(sum==x) {
				return true;
			}
			
		}
		return false;
	}
	public static void leftRotateByOne(int[] arr)
    {
		for(int i = 0; i < 2; i++){    
            int j, last;    
            //Stores the last element of array    
            last = arr[arr.length-1];    
            
            for(j = arr.length-1; j > 0; j--){    
                //Shift element of array by one    
                arr[j] = arr[j-1];    
            }    
            //Last element of array will be added to the start of array.    
            arr[0] = last;    
        }  
    }
    static class Node {
        String s;
        int val;
 
        public Node(String a, int v) {
            val = v;
            s = a;
        }
    }
	 public static HashMap<String, Integer> sortByValue(HashMap<String, Integer> hm)
	    {
	        // Create a list from elements of HashMap
	        List<Map.Entry<String, Integer> > list =
	               new LinkedList<Map.Entry<String, Integer> >(hm.entrySet());
	 
	        // Sort the list
	        Collections.sort(list, new Comparator<Map.Entry<String, Integer> >() {
	            public int compare(Map.Entry<String, Integer> o1,
	                               Map.Entry<String, Integer> o2)
	            {
	                return -(o1.getValue()).compareTo(o2.getValue());
	            }
	        });
	         
	        // put data from sorted list to hashmap
	        HashMap<String, Integer> temp = new LinkedHashMap<String, Integer>();
	        for (Map.Entry<String, Integer> aa : list) {
	            temp.put(aa.getKey(), aa.getValue());
	        }
	        return temp;
	    }
	
 
static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
	
	
static void reduceFraction(int x, int y) 
{ 
    int d; 
    d = gcd(x, y); 
  
    x = x / d; 
    y = y / d; 
  if(x>0 && y<0) {
	  x=-x;
	  y=-y;
  }
    System.out.println( x + "/" + y); 
} 
	
	static int gcd(int a, int b) {
		return a%b == 0 ? b : gcd(b,a%b);
	}
	
	static boolean[] sieve(int n) {
		
		boolean isPrime[] = new boolean[n+1];
		for(int i = 2; i <= n; i++) {
			if(isPrime[i]) continue;
			for(int j = 2*i; j <= n; j+=i) {
				isPrime[j] = true;
			}
		
		}
		return isPrime;
		
	}
}