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

    public class Main {

	static FastScanner scn = new FastScanner();
	static PrintWriter out = new PrintWriter(System.out);

	public static void main(String[] HastaLaVistaLa) {
		// Running Number Of TestCases (t)
		int t = scn.nextInt();
		while(t-- > 0)
			solve();
		out.close();
	}

	static long MOD = 998244353L;
	static int[] dp;
	public static void solve() {
		// Main Solution (AC)
		int n = scn.nextInt();
		if(n == 2) {
			out.println(-1);
			return;
		}
		int[][] board = new int[n][n];
		int start = 1;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				board[i][j] = start;
				start++;
			}
		}
		for(int i = 0; i + 1 < n; i++) {
			for(int j = 0; j < n; j++) {
				if(j % 2 == 0) {
					int temp = board[i][j];
					board[i][j] = board[i+1][j];
					board[i+1][j] = temp;
				}
			}
		}
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				out.print(board[i][j] + " ");
			}
			out.println();
		}

	}
 
	public static long binpow(long n, long m, long mod) {
	        long res = 1;
	        while (m > 0) {
	            if (m % 2 == 1) {
	                res *= n;
	                res %= mod;
	                m--;
	            }
	            n *= n;
	            n %= mod;
	            m /= 2;
	        }
	        return res;
    	}

    	// To calculate the Factorial in Combinatorics Problems
	static long[] fact;
    	public static void factorial(int n) {
    		fact = new long[n];
		Arrays.fill(fact, 1);
		for(int i = 1; i < n; i++) fact[i] *= ( ((long) i * (fact[i-1])) % MOD);
    	}

	public static HashMap<Character, Integer> CountCharFrequencies(char[] arr) {
		HashMap<Character, Integer> map = new HashMap<>();
		for (char i : arr) if (map.containsKey(i)) map.put(i, map.get(i) + 1); else map.put(i, 1);
		return map;
	}

	public static HashMap<Integer, Integer> CountIntFrequencies(int[] arr) {
		HashMap<Integer, Integer> map = new HashMap<>();
		for (int i : arr) if (map.containsKey(i)) map.put(i, map.get(i) + 1); else map.put(i, 1);
		return map;
	}

	// Number of Divisor for Range [l, r]
	public static int[] NumberOFDivisors(int l, int r) {
		int[] arr = new int[l - r + 1];
		for(int i = l; i <= r; i++) for(int j = i; j <= r; j += i) arr[j]++;
		return arr;
	}

	public static int LowerBound(int a[], int x) { // x is the target value or key

		  int l = -1,r = a.length;
		  while(l + 1 < r) {
		    int m = (l + r) >>> 1;
		    if(a[m] >= x) r = m;
		    else l = m;

		  }
		  return r;
	}

	static boolean[] prime;
	public static void sieveOfEratosthenes(int n) {

        	prime = new boolean[n+1];
	        for(int i=0;i<n;i++)
	            prime[i] = true;
	        for(int p = 2; p*p <=n; p++) {
	            if(prime[p] == true) {
	                for(int i = p*p; i <= n; i += p)
	                    prime[i] = false;
	            }
	        }
    	}

	public static int UpperBound(int[] a, int x) {// x is the key or target value

		    int l = -1,r = a.length;
		    while(l + 1 < r) {
		       int m = (l + r) >>> 1;
		       if(a[m] <= x) l = m;
		       else r = m;
		    }
		    return l + 1;
	}

    	public static long lcm(long a, long b) {
		return (a * b) / gcd(a, b);
	}

	public static long gcd(long a, long b) {
		if (a == 0)
			return b;
		return gcd(b % a, a);
	}

	public static void sort(int[] arr) {
		Random rand = new Random();
		int n = arr.length;
		for(int i = 0; i<n; i++) {
			swap(arr, i, rand.nextInt(n));
		}
		Arrays.sort(arr);
	}

	public static void swap(int[] arr, int i, int j) {
		if(i!=j) {
			arr[i] ^= arr[j];
			arr[j] ^= arr[i];
			arr[i] ^= arr[j];
		}
	}
     
	public static void sortbyColumn(int[][] arr, int col) {
		Arrays.sort(arr, new Comparator<int[]>() {
			public int compare(final int[] entry1, final int[] entry2) {
				if (entry1[col] > entry2[col])
					return 1;
				else
					return -1;
			}
		});
	}

	public static void ArraySort2D(double[][] arr, int xy) {
		// xy == 0, for sorting wrt X-Axis
		// xy == 1, for sorting wrt Y-Axis
		Arrays.sort(arr, Comparator.comparingDouble(o -> o[xy]));
	}
     
	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[] readIntArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long[] readLongArray(int n) {
			long[] a=new long[n];
			for (int i=0; i<n; i++) a[i]=nextLong();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
}