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.ArrayList;
	import java.util.Arrays;
	import java.util.Random;
	import java.util.StringTokenizer;


	
	 
	public class A { 
		// author: Tarun Verma
		static FastScanner sc = new FastScanner();
		static int inf = Integer.MAX_VALUE;
		static int mod = 1000000007;
			
		public static int digi(long n) {
			int count = 0;
			while(n != 0) {
				n /= 10;
				count++;
			}
			return count;
		}
		public static void main(String[] args) {
			int t;
			t = 1;
			t =sc.nextInt();
			outer: for(int tt = 0;tt<t;tt++) {
				
				int n = sc.nextInt();
				if(n == 2) {System.out.println(-1); continue outer;}
				long arr[][] = new long[n][n];
				long st = 1;long ed = n*n;
				boolean f = true;
				for(int i = 0;i<n;i++) {
					if(i % 2 == 0) {
						for(int j = 0;j<n;j++) {
							if(f) {
								f = false;
								arr[i][j] = st;
								st++;
							} else {
								f = true;
								arr[i][j] = ed;
								ed--;
							}
						}
						if(i == n-1) {
							long temp = arr[0][0];
							arr[0][0] = arr[i][n-1];
							arr[i][n-1] = temp;
						}
					} else {
						for(int j=n-1;j>=0;j--) {
			                if(f) {
			                    f = false;
			                    arr[i][j] = st;
			                    st++;
			                }
			                else {
			                    f = true;
			                    arr[i][j] = ed;
			                    ed--;
			                }
			            }
			            if(i == n-1) {
			            	long temp = arr[0][0];
							arr[0][0] = arr[i][0];
							arr[i][0] = temp;
			            }
					}
				}
				
				for(int i = 0;i<n;i++) {
					for(int j = 0;j<n;j++) {
						System.out.print(arr[i][j] + " ");
					} System.out.println();
				}
				
			}
				
		}
		static boolean isPalindrom(char[] arr, int i, int j) {
			boolean ok = true;
			while(i<=j) {
				if(arr[i] != arr[j]) {
					ok = false;
					break;
				}
				i++;
				j--;
			}
			return ok;
		}
		static void printArr(int arr[]) {
			for(int i: arr) {
				System.out.print(i+" ");
			} System.out.println();
		}
		static int max(int a, int b) {return Math.max(a, b);}
		static int min(int a, int b) {return Math.min(a, b);}
		static int maxArr(int a[]) { 
			ruffleSort(a);
			return a[a.length - 1];
		}
		static int minArr(int a[]) { 
			ruffleSort(a);
			return a[0];
		}
		static void swap(int[] arr, int i, int j) {
			int temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
		static long gcd(long a, long b) {
			if (b==0) return a;
			return gcd(b, a%b);
		}
		static void ruffleSort(int[] a) {
			int n=a.length;
			Random r=new Random();
			for (int i=0; i<a.length; i++) {
				int oi=r.nextInt(n); int temp=a[i];
				a[i]=a[oi];
				a[oi]=temp;
			}
			Arrays.sort(a);
		}
		public static int binarySearch(int a[], int target) {
			int left = 0;
			int right = a.length - 1;
			int mid = (left+ right) / 2;
			int i = 0;
			while(left <= right) {
				if(a[mid] <= target) {
					i = mid+1;
					left = mid + 1;
				} else {
					right = mid - 1;
				}
				mid = (left + right) / 2;
			}
			return i;
		}
		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;
			}
			int[][] read2dArray(int n, int m){
				int arr[][] = new int[n][m];
				for(int i= 0;i<n;i++) {
					for(int j = 0;j<m;j++) {
						arr[i][j] = nextInt();
					}
				}
				return arr;
			}
			
			ArrayList<Integer> readArrayList(int n){
				ArrayList<Integer> arr = new ArrayList<Integer>();
				for(int i = 0;i<n;i++) {
					int a = nextInt();
					arr.add(a);
				}
				return arr;
			}
			long nextLong() {
				return Long.parseLong(next());
			}
		}
		
		/*
		 * when you thing of giving up, think that other are hardworking!!!
		 */
	}