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.BigInteger;
import java.util.*;
import static java.lang.Math.PI;
import static java.lang.System.in;
import static java.lang.System.out;
import static java.lang.System.err;

public class C {    
    static int dx[] = {1,-1,0, 0};
    static int dy[] = {0, 0,1,-1};
    static public void main(String... args) throws Exception {   
        Foster sc = new Foster();
        PrintWriter p = new PrintWriter(out);
        int t = sc.nextInt();
        while(t--!=0){
            int n = sc.nextInt();
            int a[][] = new int[n][n];
            for(int i = 0; i < n; i++)  Arrays.fill(a[i], -1);
            if(n==2){
                p.println("-1");
            }
            else if(n==3){
                p.println("2 9 7");
                p.println("4 6 3");
                p.println("1 8 5");
            }
            else{
                PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
                    public int compare(Integer a, Integer b){
                        return (int)a-(int)b;
                    }
                });
                for(int i = 0; i < n*n; i++){
                    pq.add(i+1);
                }
                for(int i = 0; i < n; i++){
                    for(int j = 0; j < n; j++){
                        TreeSet<Integer> tree = new TreeSet<>();
                        for(int k = 0; k < 4; k++){
                            int nx = dx[k] + i;
                            int ny = dy[k] + j;
                            if(nx>=0 && nx < n && ny>=0 && ny<n){
                                tree.add(a[nx][ny]);
                            }
                        }
                        ArrayList<Integer> removed = new ArrayList<>();
                        int taken = -1;
                        while(!pq.isEmpty()){
                            int cur = pq.poll();
                            boolean cant = false;
                            for(int it : tree){
                                if(Math.abs(it-cur)==1) cant = true;
                            }
                            if(!cant){
                                taken = cur;
                                break;
                            }
                            removed.add(cur);
                        }
                        a[i][j] = taken;
                        for(int it : removed)   pq.add(it);
                    }
                }
                boolean found = false;
                for(int i = 0; i < n; i++){
                    for(int j = 0; j < n; j++){
                        if(a[i][j]==-1){
                            found = true;
                            a[i][j] = 1;
                        }
                    }
                }
                if(found){
                    a[0][0] = pq.poll();
                }
                for(int i = 0; i < n; i++){
                    for(int j = 0; j < n; j++){
                        p.print(a[i][j] + " ");
                    }
                    p.println();
                }
            }

        }
        p.close();
    }
    
    static long[] sort(long a[]){
        ArrayList<Long> arr = new ArrayList<>();
        for(long i : a){
            arr.add(i);
        }
        Collections.sort(arr);
        for(int i = 0; i < arr.size(); i++){
            a[i] = arr.get(i);
        }
        return a;
    }
    static int[] sort(int a[]){
        ArrayList<Integer> arr = new ArrayList<>();
        for(int i : a){
            arr.add(i);
        }
        Collections.sort(arr);
        // Collections.reverse(arr);
        for(int i = 0; i < arr.size(); i++){
            a[i] = arr.get(i);
        }
        return a;
    }
    
    
/* 
*/    
/*
1. Check overflow in pow function or in general
2. Check indices of read array function
3. Think of an easier solution because the problems you solve are always easy
4. Check iterator of loop
5. If still doesn't work, then jump from the 729th floor 'coz "beta tumse na ho paayega"

    Move to top!!
*/
    static class Foster {
        BufferedReader br = new BufferedReader(new InputStreamReader(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());
        }
        int[] intArray(int n) {                   // Check indices
            int arr[] = new int[n];
            for(int i = 0; i < n; i++) {
                arr[i] = nextInt();
            }
            return arr;
        }
        long[] longArray(int n) {                 // Check indices
            long arr[] = new long[n];
            for(int i = 0; i < n; i++) {
                arr[i] = nextLong();
            }
            return arr;
        }
        int[] getBits(int n) {                   //in Reverse Order
            int a[] = new int[31];
            for(int i = 0; i < 31; i++) {
                if(((1<<i) & n) != 0)
                    a[i] = 1;
            }
            return a;
        }
        static long pow(long... a) {
            long mod = Long.MAX_VALUE;
            if(a.length == 3)   mod = a[2];
            long res = 1;
            while(a[1] > 0) {
                if((a[1] & 1) == 1)
                    res = (res * a[0]) % mod;
                a[1] /= 2;
                a[0] = (a[0] * a[0]) % mod;
            }
            return res;
        }
    }
}