Problem: Sasha likes investigating different math objects, for example, magic squares. But Sasha understands that magic squares have already been studied by hundreds of people, so he sees no sense of studying them further. Instead, he invented his own type of square — a prime square. 

A square of size n × n is called prime if the following three conditions are held simultaneously: 

  * all numbers on the square are non-negative integers not exceeding 10^5; 
  * there are no prime numbers in the square; 
  * sums of integers in each row and each column are prime numbers. 



Sasha has an integer n. He asks you to find any prime square of size n × n. Sasha is absolutely sure such squares exist, so just help him!

Input

The first line contains a single integer t (1 ≤ t ≤ 10) — the number of test cases.

Each of the next t lines contains a single integer n (2 ≤ n ≤ 100) — the required size of a square.

Output

For each test case print n lines, each containing n integers — the prime square you built. If there are multiple answers, print any.

Example

Input


2
4
2


Output


4 6 8 1
4 9 9 9
4 10 10 65
1 4 4 4
1 1
1 1

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;

public class B {   
    public static 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++){
                for(int j = 0; j < n; j++){
                    if(i==j){
                        a[i][j] = 1;
                    }
                }
            }
            int idx = 1;
            for(int i = 0; i < n-1; i++){
                for(int j = 0; j < n; j++){
                    if(idx==j){
                        a[i][j] = 6;
                    }
                }
                idx++;
            }
            a[n-1][0] = 6;
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    p.print(a[i][j] + " ");
                }
                p.println();
            }
            
            // int row[] = new int[n];
            // int col[] = new int[n];
            // for(int i = 0; i < n; i++){
            //     int sum = 0;
            //     for(int j = 0; j < n; j++){
            //         sum += a[i][j];
            //     }
            //     row[i] = sum;
            // }
            // for(int i = 0; i < n; i++){
            //     int sum = 0;
            //     for(int j = 0; j < n; j++){
            //         sum += a[j][i];
            //     }
            //     col[i] = sum;
            // }
            // sc.watch(row);
            // sc.watch(col);
            
        }
        p.close();
    }

    static int[] sort(int a[]){
        ArrayList<Integer> arr = new ArrayList<>();
        for(int i : a){
            arr.add(i);
        }
        Collections.sort(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;
        }
        static void print(Object... o) {
            for(Object next : o) {
                System.err.print(next + " ");
            }
        }
        static void println(Object... o) {
            for(Object next : o) {
                System.err.print(next + " ");
            }
            System.err.println();
        }
        static void watch(Object...a) throws Exception {
            int i = 1;
            for (Object o: a) {
                boolean found = false;
                if (o.getClass().isArray()) {
                    String type = o.getClass().getName().toString();
                    switch (type) {
                        case "[I": {
                            int[] test = (int[]) o;
                            println(i + " : " + Arrays.toString(test));
                            break;
                        }
                        case "[[I": {
                            int[][] obj = (int[][]) o;
                            println(i + " : " + Arrays.deepToString(obj));
                            break;
                        }
                        case "[J": {
                            long[] obj = (long[]) o;
                            println(i + " : " + Arrays.toString(obj));
                            break;
                        }
                        case "[[J": {
                            long[][] obj = (long[][]) o;
                            println(i + " : " + Arrays.deepToString(obj));
                            break;
                        }
                        case "[D": {
                            double[] obj = (double[]) o;
                            println(i + " : " + Arrays.toString(obj));
                            break;
                        }
                        case "[[D": {
                            double[][] obj = (double[][]) o;
                            println(i + " : " + Arrays.deepToString(obj));
                            break;
                        }
                        case "[Ljava.lang.String": {
                            String[] obj = (String[]) o;
                            println(i + " : " + Arrays.toString(obj));
                            break;
                        }
                        case "[[Ljava.lang.String": {
                            String[][] obj = (String[][]) o;
                            println(i + " : " + Arrays.deepToString(obj));
                            break;
                        }
                        case "[C": {
                            char[] obj = (char[]) o;
                            println(i + " : " + Arrays.toString(obj));
                            break;
                        }
                        case "[[C": {
                            char[][] obj = (char[][]) o;
                            println(i + " : " + Arrays.deepToString(obj));
                            break;
                        }
                        default: {
                            println(i + " : type not identified");
                            break;
                        }
                    }
                    found = true;
                }
                if (o.getClass() == ArrayList.class) {
                    println(i + " : LIST = " + o);
                    found = true;
                }
                if (o.getClass() == TreeSet.class) {
                    println(i + " : SET = " + o);
                    found = true;
                }
                if (o.getClass() == TreeMap.class) {
                    println(i + " : MAP = " + o);
                    found = true;
                }
                if (o.getClass() == HashMap.class) {
                    println(i + " : MAP = " + o);
                    found = true;
                }
                if (o.getClass() == LinkedList.class) {
                    println(i + " : LIST = " + o);
                    found = true;
                }
                if (o.getClass() == PriorityQueue.class) {
                    println(i + " : PQ = " + o);
                    found = true;
                }
                if (!found) {
                    println(i + " = " + o);
                }
                i++;
            }
        }
    }
}