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:
//package Coding;

import java.io.*;
import java.math.BigInteger;
import java.nio.Buffer;
import java.util.*;

public class Solve {
    public static FastReader in = new FastReader();
    static Comparator<int[]> comp = new Comparator<int[]>() {
        public int compare(int[] a, int[] b) {
            for (int i = 0; i < a.length; i++) {
                if (a[i] < b[i]) return -1;
                else if (a[i] > b[i]) return 1;
            }
            return 0;
        }
    };

    // Comparators for array
    static Comparator<int[]> sortByFirst = new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return Integer.compare(o1[0], o2[0]);
        }
    };
    static Comparator<int[]> sortBySecond = new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return Integer.compare(o1[1], o2[1]);
        }
    };

    // Main
    public static void main(String[] args) throws IOException {
        int t = in.nextInt();
        for (int i = 0; i < t; ++i) {
            int n = in.nextInt();
            if (n == 1) {
                System.out.println(1);
            } else if (n == 2) {
                System.out.println(-1);
            } else {
                int s = 1;
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k < n; k++) {
                        System.out.print(s + " ");
                        s += 2;
                        if (s > n * n) {
                            s = 2;
                        }
                    }
                    System.out.println();
                }
            }
        }


    }



    // Fast Reader
    static class FastReader {
        final private int BUFFER_SIZE = 1 << 16;
        private int MAX_LINE_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer, lineBuf;
        private int bufferPointer, bytesRead;

        public FastReader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            lineBuf = new byte[MAX_LINE_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public FastReader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public boolean hasNext() throws IOException {
            byte c;
            while ((c = read()) != -1) {
                if (c > ' ') {        // Find first byte bigger than ' '
                    bufferPointer--;
                    return true;
                }
            }
            return false;
        }

        // return the next line that contains at least one character > ' '
        public String nextLine() throws IOException {
            int ctr = 0;
            byte c;
            boolean empty = true;
            while ((c = read()) != -1) {
                if (c == '\r') continue;    // ignore '\r'
                if (c == '\n') {
                    if (empty) {
                        ctr = 0;
                        continue;
                    } // read only spaces etc. until \n
                    else break;
                }
                if (ctr == MAX_LINE_SIZE) {
                    MAX_LINE_SIZE *= 2;
                    lineBuf = Arrays.copyOf(lineBuf, MAX_LINE_SIZE);
                }
                lineBuf[ctr++] = c;
                if (c > ' ') empty = false;
            }
            return new String(lineBuf, 0, ctr);
        }

        public String next() throws IOException {
            int ctr = 0;
            byte c = read();
            while (c <= ' ') c = read();
            while (c > ' ') {
                if (ctr == MAX_LINE_SIZE) {
                    MAX_LINE_SIZE *= 2;
                    lineBuf = Arrays.copyOf(lineBuf, MAX_LINE_SIZE);
                }
                lineBuf[ctr++] = c;
                c = read();
            }
            return new String(lineBuf, 0, ctr);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg) return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg) return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }
            if (neg) return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead) fillBuffer();
            if (bytesRead <= 0) return -1;  // No data
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null) return;
            din.close();
        }
    }

    // Other Helper Methods / Debug
    public static int[] createArray(int n) throws IOException {
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = in.nextInt();
        }
        return arr;
    }

    public static void printArray(int[] arr) {
        for (int s : arr) {
            System.out.print(s + " ");
        }
        System.out.println();
    }

    public static void print2DArray(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }


}