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.math.*;
import java.util.*;
public class Q3 {
	static int INF = (int)(1e9);
	static long mod = (long)(1e9)+7;
	static long mod2 = 998244353;
	static long[] segtree;
	static char[] curans;
	static long ans;	
	static String S;
	static ArrayList<Integer>[] graph;
	static boolean[] vis;
	static int[] a;
	static int N;
	static long K;
	static long[] fact;
	static ArrayList<Long> pos;
	static ArrayList<Long> neg;
	static long[] max;
	static int[] dp;
	public static void main(String[] args) {  //Cash out
		/**/
		FastScanner I = new FastScanner(); //Input
		OutPut O = new OutPut(); //Output
		int T = I.nextInt();
		StringBuilder ret = new StringBuilder();
		while (T-- > 0) {
			int N = I.nextInt();
			
			int[][] ans = new int[N][N];
			
			if (N == 1) {
				ret.append(1 + "\n");
				continue;
			}
			
			if (N == 2) {
				ret.append(-1 + "\n");
				continue;
			}
			
			
			int odd = 1;
			int even = 4;
			for (int i = 0; i < N - 1; i++) {
				
				if (i % 2 == 0) {
					for (int j = 0; j < N; j++) {
						ans[i][j] = odd;
						odd += 2;
					}
				}
				
				else {
					for (int j = 0; j < N; j++) {
						ans[i][j] = even;
						even += 2;
					}
				}
			}
			
			if ((N - 1) % 2 == 0) {
				int in = 0;
				
				while (even <= N * N) {
					ans[N - 1][in] = even;
					
					even += 2;
					in += 1;
				}
				
				while (odd <= N * N) {
					ans[N - 1][in] = odd;
					
					odd += 2;
					in += 1;
				}
				
				ans[N - 1][N - 1] = 2;
			}
			
			else {
				int in = 0;
				while (even <= N * N) {
					ans[N - 1][in] = even;
					
					even += 2;
					in += 1;
				}
				
				ans[N - 1][N - 1] = 2;
			}
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					ret.append(ans[i][j] + " ");
				}
				ret.append("\n");
			}
		}
		O.pln(ret);
	}
	public static double[][] matrix_exp(double[][] a, long exp, long mod) {
		int R = a.length;
		int C = a[0].length;
		double[][] ans = new double[R][C];
		
		boolean mult_yet = false;
		
		while (exp > 0) {
			if (exp % 2 == 1) {
				if (!mult_yet) {
					mult_yet = true;
					for (int i = 0; i < R; i++) {
						for (int j = 0; j < C; j++) {
							ans[i][j] = a[i][j]; 
						}
					}
				}else {
					double[][] new_ans = mult(ans, a, mod);
					for (int i = 0; i < R; i++) {
						for (int j = 0; j < C; j++) {
							ans[i][j] = new_ans[i][j]; 
						}
					}
				}
			}
			
			double[][] new_a = mult(a, a, mod); // a = a^2 (binary exponentiation on matrices)
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C; j++) {
					a[i][j] = new_a[i][j]; 
				}
			}
			exp /= 2;
		}
		
		return ans;
	}
	public static double[][] mult(double[][] a, double[][] b, long mod) {
		int r1 = a.length;
		int c1 = a[0].length;
		int r2 = b.length;
		int c2 = b[0].length;
		//Requires: c1 = r2
		
		double[][] ans = new double[r1][c2];
		for (int r = 0; r < r1; r++) {
			for (int c = 0; c < c2; c++) {
				//Dot product of (a[r])^T and b[c] (as vectors in R^n (n = c1 = r2))
				double[] col_vector = new double[r2];
				double[] row_vector = new double[c1];
				
				for (int i = 0; i < r2; i++) {
					col_vector[i] = b[i][c];
				}
				for (int i = 0; i < c1; i++) {
					row_vector[i] = a[r][i]; 
				}
				
				ans[r][c] = dot_product(row_vector, col_vector, mod);
			}
		}
		return ans;
	}
	
	public static double dot_product(double[] a, double[] b, long mod) {
		double ans = 0;
		int N = a.length; //Requires: a and b are both vectors in R^n
		for (int i = 0; i < N; i++) {
			ans += a[i] * b[i];
		}
		return ans;
	}
	public static double max(double a, double b) {return Math.max(a, b);}
	public static double min(double a, double b) {return Math.min(a, b);}
	public static long min(long a, long b) {return Math.min(a,b);}
	public static long max(long a, long b) {return Math.max(a,b);}
	public static int min(int a, int b) {return Math.min(a,b);}
	public static int max(int a, int b) {return Math.max(a,b);}
	public static long abs(long x) {return Math.abs(x);}
	public static long abs(int x) {return Math.abs(x);}
	public static long ceil(long num, long den) {long ans = num/den; if (num%den!=0) 
	ans++; return ans;}
	public static long GCD(long a, long b) {
		if (a==0||b==0) return max(a,b);
		return GCD(min(a,b),max(a,b)%min(a,b));
	}
	public static long FastExp(long base, long exp, long mod) {
		long ans=1;
		while (exp>0) {
			if (exp%2==1) ans*=base;
			exp/=2;
			base*=base;
			base%=mod;
			ans%=mod;
		}
		return ans;
	}
	public static long ModInv(long num,long mod) {return FastExp(num,mod-2,mod);}
	public static int pop(long x) { //Returns number of bits within a number
		int cnt = 0;
		while (x>0) {
			if (x%2==1) cnt++;
			x/=2;
		}
		return cnt;
	}
	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());}
		long nextLong() {return Long.parseLong(next());};
		double nextDouble() {return Double.parseDouble(next());}
	}
	static class OutPut{
		PrintWriter w = new PrintWriter(System.out);
		void pln(double x) {w.println(x);w.flush();}
		void pln(boolean x) {w.println(x);w.flush();}
		void pln(int x) {w.println(x);w.flush();}
		void pln(long x) {w.println(x);w.flush();}
		void pln(String x) {w.println(x);w.flush();}
		void pln(char x) {w.println(x);w.flush();}
		void pln(StringBuilder x) {w.println(x);w.flush();}
		void pln(BigInteger x) {w.println(x);w.flush();}
		void p(int x) {w.print(x);w.flush();}
		void p(long x) {w.print(x);w.flush();}
		void p(String x) {w.print(x);w.flush();}
		void p(char x) {w.print(x);w.flush();}
		void p(StringBuilder x) {w.print(x);w.flush();}
		void p(BigInteger x) {w.print(x);w.flush();}
		void p(double x) {w.print(x);w.flush();}
		void p(boolean x) {w.print(x);w.flush();}
	}
}