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.*;
import java.util.*;




public class C680 {
	static 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; 
        }
        int[] nextArray(int n)
        {
        	int arr[]=new int[n];
        	for(int i=0;i<n;i++)
        		arr[i]=nextInt();
        	return arr;
        }
    } 
	private static int V ; 
    private static List<List<Integer>> adj; 
    public C680(int V)  
    { 
        this.V = V; 
        adj = new ArrayList<>(V); 
          
        for (int i = 0; i < V; i++) 
            adj.add(new LinkedList<>()); 
    } 
	static void sum(int nums[],int i,ArrayList<Integer> a,ArrayList<Integer> b,HashSet<String> hSet)
	{
		if(i==nums.length)
		{
			Collections.sort(a);
			Collections.sort(b,Collections.reverseOrder());
			String string=a.toString()+b.toString();
			if(hSet.contains(string))
				return;
			else {
				
			}
		}
	}
	static long gcd(long a, long b)
    {
		//System.out.println(a+","+b);
        // Everything divides 0 
        if (a == 0)
          return b;
        if (b == 0)
          return a;
      
        // base case
        if (a == b)
            return a;
      
        // a is greater
        if (a > b)
            return gcd(a-b, b);
        return gcd(a, b-a);
    }
	static long findGCD(long arr[], int n) 
    { 
        long result = 0; 
        for (long element: arr){ 
            result = gcd(result, element); 
  
            if(result == 1) 
            { 
               return 1; 
            } 
        } 
  
        return result; 
    } 
		private static boolean isCyclicUtil(int i, boolean[] visited, 
			            boolean[] recStack)  
			{ 
			
			// Mark the current node as visited and 
			// part of recursion stack 
			if (recStack[i]) 
			return true; 
			
			if (visited[i]) 
			return false; 
			
			visited[i] = true; 
			
			recStack[i] = true; 
			List<Integer> children = adj.get(i); 
			
			for (Integer c: children) 
			if (isCyclicUtil(c, visited, recStack)) 
			return true; 
			
			recStack[i] = false; 
			
			return false; 
			} 
			
			
			
			// Returns true if the graph contains a  
			// cycle, else false. 
			// This function is a variation of DFS() in  
			// https://www.geeksforgeeks.org/archives/18212 
			private static boolean isCyclic()  
			{ 
			
			// Mark all the vertices as not visited and 
			// not part of recursion stack 
			boolean[] visited = new boolean[V]; 
			boolean[] recStack = new boolean[V]; 
			
			
			// Call the recursive helper function to 
			// detect cycle in different DFS trees 
			for (int i = 0; i < V; i++) 
			if (isCyclicUtil(i, visited, recStack)) 
			return true; 
			
			return false; 
			} 
			static boolean same(int []arr)
			{
				for(int i=1;i<arr.length;i++)
					if(arr[i]!=arr[0]&&arr[0]!=Integer.MAX_VALUE&&arr[i]!=Integer.MAX_VALUE)
						return false;
				return true;
			}
			static int inv(int[] arr)
			{
				int tot=0;
				for(int i=0;i<arr.length;i++)
				{
					for(int j=i+1;j<arr.length;j++)
						if(arr[i]>arr[j])
							tot++;
					
				}
				return tot;
			}
			static boolean ab(int[] a,int[] b,int i,int k,int inv,int[] p)
			{
				if(i==a.length)
				{
					if(inv(b)<=inv)
						return true;
					else
						return false;
				}
				for(int j=k;j>=1;j--)
				{
					int in=a.length-a.length%j-1;
					if(p[in]==0)
					{
						b[i]=j;
						p[in]=j;
						if(ab(a, b, i+1, k, inv, p))
								return true;
					}
					else {
						b[i]=p[in];
					}
					
				}
				return false;
			}
			static int prime(int n)
			{
				for(int i=n;;i++)
				{
					boolean flag=true;
					for(int j=2;j<i;j++)
						if(i%j==0)
						{
							flag=false;
							break;
						}
					if(flag)
						return i;
				}
				
			}
			static int cal(int a,int b,int x,int y,HashSet<String> hs)
			{
				int hcf=(int)gcd(a, b);
				a=a/hcf;
				b=b/hcf;
				String s=a+","+b;
				if(hs.contains(s))
					return 0;
				if(a==x&&b==y)
					return 0;
				hs.add(s);
				int ans=0;
				if(a/b==a%b)
					ans=1;
				if(a<x)
					ans+=cal(a+1, b, x, y, hs);
				if(b<y)
					ans+=cal(a, b+1, x, y, hs);
				return ans;
			}
			static int helper(String s,String t,int i,int j,int prev,int max,HashMap<String , Integer> hm)
			{
				//System.out.println(i+","+j+","+prev);
				if(j-t.length()==0)
				{
					//System.out.println(pq);
				
					return max;
				}
				else if (i-s.length()==0) {
					return -1;
				}
				else if(s.substring(i).equals(t.substring(j)))
					return Math.max(max,i-prev);
				String key=i+","+j+","+prev;
				if(hm.containsKey(key))
					return hm.get(key);
				int curr=helper(s, t, i+1, j, prev, max,hm);
				if(s.charAt(i)==t.charAt(j))
				{
					if(prev!=-1)
					max=Math.max(max, i-prev);
					hm.put(key,Math.max(curr,helper(s, t, i+1, j+1,i,max,hm)));
					return hm.get(key);
				}
				hm.put(key, curr);
				return hm.get(key);
			}
			static boolean helper(HashMap<Integer, int[]> hm,int i,StringBuilder sb,int m,int[] count)
			{
				if(i==m)
				{
					return true;
				}
				int[] arr=hm.get(i);
				for(int j=0;j<arr.length;j++)
				{
					//System.out.println(i+","+arr[i]);
					if(count[arr[j]]<m/2-1)
					{
						count[arr[j]]++;
						if(helper(hm, i+1, sb, m, count))
						{
							sb.append(" "+(arr[j]+1));
							return true;
						}
						count[arr[j]]--;
					}
				}
				return false;
			}
			static int helper(int[] arr,int sum1,int sum2,int i)
			{
				if(i==arr.length)
				{
//					System.out.println(sum1+","+sum2);
					if(sum1!=sum2)
						return 0;
					else {
						return Integer.MAX_VALUE/2;
					}
				}
				int ans=1+helper(arr, sum1, sum2, i+1);
				ans=Math.min(ans,helper(arr, sum1+arr[i], sum2, i+1));
				ans=Math.min(ans,helper(arr, sum1, sum2+arr[i], i+1));
				return ans;
			}
		public static void main(String[] args)throws IOException
		{
			BufferedReader bReader=new BufferedReader(new InputStreamReader(System.in));
			FastReader fs=new FastReader();
			int T=fs.nextInt();
			StringBuilder sb=new StringBuilder();
			while(T-->0)
			{
				int n=fs.nextInt();
				int[][] arr=new int[n][n];
				if(n==1)
					sb.append(1);
				else if(n==2)
					sb.append(-1);
				else {
					int c=1;
					for(int i=0;i<n;i++)
						arr[i][i]=c++;
					int d=0;
					for(int i=1;i<n;i++)
					{
						for(int j=0;j<n-i;j++)
							arr[j][i+j]=c++;
						for(int j=i;j<n;j++)
							arr[j][j-i]=c++;
					}
					for(int i=0;i<n;i++)
					{
						for(int j=0;j<n;j++)
						{
							sb.append(arr[i][j]).append(" ");
						}
						if(i!=n-1)
						sb.append("\n");
					}
				}
				sb.append("\n");
//				System.out.println(sb);
			}
			System.out.println(sb);
		}
}