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 com.company;

import java.awt.image.AreaAveragingScaleFilter;
import java.io.*;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.*;

public class Main
{
    public static void main(String[] args) throws IOException {
        OutputStream outputStream = System.out;
        FastReader in = new FastReader();
        PrintWriter out = new PrintWriter(outputStream);
        PROBLEM solver = new PROBLEM();
        int t=1;
        t = in.nextInt();
        for(int i=0;i<t;i++){
            solver.solve(in, out);
        }
        out.close();
    }

    static class PROBLEM
    {
        public void solve(FastReader in,PrintWriter out) {

            int n = in.nextInt();

            if(n == 1) out.println(1);
            else if(n == 2) out.println(-1);
            else if(n == 3){
                int[][] a = new int[3][3];
                a[0][0] = 2;
                a[0][1] = 9;
                a[0][2] = 7;
                a[1][0] = 4;
                a[1][1] = 6;
                a[1][2] = 3;
                a[2][0] = 1;
                a[2][1] = 8;
                a[2][2] = 5;

                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        out.print(a[i][j]+ " ");
                    }
                    out.println();
                }

            }else{

                int[][] a = new int[n][n];

                int ctr = 1;
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j+=2) {
                        a[i][j] = ctr;
                        ctr++;
                    }
                }
                for (int i = 0; i < n; i++) {
                    for (int j = 1; j < n; j+=2) {
                        a[i][j] = ctr;
                        ctr++;
                    }
                }

                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        out.print(a[i][j]+ " ");
                    }
                    out.println();
                }
            }
        }
    }

    static boolean isSquare(double a){
        boolean isSq = false;
        double b = Math.sqrt(a);
        double c = Math.sqrt(a) - Math.floor(b);

        if(c == 0) isSq = true;

        return isSq;
    }

    static int power(int x, long y, int p)
    {
        int res = 1; // Initialize result

        x = x % p; // Update x if it is more than or
        // equal to p

        if (x == 0)
            return 0; // In case x is divisible by p;

        while (y > 0)
        {

            // If y is odd, multiply x with result
            if ((y & 1) != 0)
                res = (res * x) % p;

            // y must be even now
            y = y >> 1; // y = y/2
            x = (x * x) % p;
        }
        return res;
    }

    public static class Pair<U extends Comparable<U>, V extends Comparable<V>> implements Comparable<Pair<U, V>> {
        public U x;
        public V y;

        public Pair(U x, V y) {
            this.x = x;
            this.y = y;
        }

        public int hashCode() {
            return (x == null ? 0 : x.hashCode() * 31) + (y == null ? 0 : y.hashCode());
        }

        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            Pair<U, V> p = (Pair<U, V>) o;
            return (x == null ? p.x == null : x.equals(p.x)) && (y == null ? p.y == null : y.equals(p.y));
        }

        public int compareTo(Pair<U, V> b) {
            int cmpU = x.compareTo(b.x);
            return cmpU != 0 ? cmpU : y.compareTo(b.y);
        }

        public String toString() {
            return String.format("(%s, %s)", x.toString(), y.toString());
        }

    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                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());
        }

        char nextChar() {
            return next().charAt(0);
        }

        boolean nextBoolean() {
            return !(nextInt() == 0);
        }
        // boolean nextBoolean(){return Boolean.parseBoolean(next());}

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

    }

    //private static long binaryExpo(long )

    private static int[] mergeSort(int[] array){

        if(array.length <= 1){
            return array;
        }

        int midpoint = array.length / 2;

        int[] left = new int[midpoint];
        int[] right;

        if(array.length % 2 == 0){
            right = new int[midpoint];
        }else{
            right = new int[midpoint + 1];
        }

        for (int i = 0; i < left.length; i++) {
            left[i] = array[i];
        }

        for (int i = 0; i < right.length; i++) {
            right[i] = array[i + midpoint];
        }

        int[] result = new int[array.length];

        left = mergeSort(left);
        right = mergeSort(right);

        result = merge(left, right);

        return result;
    }

    private static int[] merge(int[] left, int[] right){

        int[] result = new int[left.length + right.length];
        int leftPointer = 0, rightPointer = 0, resultPointer = 0;

        while(leftPointer < left.length || rightPointer < right.length){

            if(leftPointer < left.length && rightPointer < right.length){

                if(left[leftPointer] < right[rightPointer]){
                    result[resultPointer++] = left[leftPointer++];
                }else{
                    result[resultPointer++] = right[rightPointer++];
                }
            }else if(leftPointer < left.length){
                result[resultPointer++] = left[leftPointer++];
            }else{
                result[resultPointer++] = right[rightPointer++];
            }
        }
        return result;
    }
}