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:

// Problem: B. Prime Square
// Contest: Codeforces - Codeforces Round #678 (Div. 2)
// URL: http://codeforces.com/contest/1436/problem/B
// Memory Limit: 256 MB
// Time Limit: 1500 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

import java.io.*;
import java.util.*;

public class Main {
    private static PrintWriter pw = new PrintWriter(System.out);
    private static InputReader sc = new InputReader();
    private static final int intmax = Integer.MAX_VALUE, intmin = Integer.MIN_VALUE;

    static class Pair{
        int first, second;
        Pair(int first, int second){
            this.first = first;
            this.second = second;
        }
    }

    static class InputReader{
        private static BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        private static StringTokenizer tk;

        private void next()throws IOException{
            while(tk == null || !tk.hasMoreTokens())   
                tk = new StringTokenizer(r.readLine());
        }

        private int nextInt()throws IOException{
            next();
            return Integer.parseInt(tk.nextToken());
        }

        private long nextLong()throws IOException{
            next();
            return Long.parseLong(tk.nextToken());
        }

        private String readString()throws IOException{
            next();
            return tk.nextToken();
        }

        private double nextDouble()throws IOException{
            next();
            return Double.parseDouble(tk.nextToken());
        }

        private int[] intArray(int n)throws IOException{
            next();
            int arr[] = new int[n];

            for(int i=0; i<n; i++)
                arr[i] = nextInt();

            return arr;
        }

        private long[] longArray(int n)throws IOException{
            next();
            long arr[] = new long[n];

            for(int i=0; i<n; i++)
                arr[i] = nextLong();

            return arr;
        }
    }
    
    private static TreeSet<Integer> primeSet;
    
    private static void genPrime(int limit){
    	boolean check[] = new boolean[limit + 1];
    	primeSet = new TreeSet<>();
    	
    	for(int i = 2; i <= limit; i++){
    		if(!check[i]){
    			primeSet.add(i);
    			
    			for(int j = i; j <= limit; j+=i)
    				check[j] = true;
    		}
    	}
    }

    public static void main(String args[])throws IOException{
    	genPrime((int)1e5);
        int t = sc.nextInt();
        while(t-->0)    solve();
        pw.flush();
        pw.close();
    }

    private static void solve()throws IOException{
		int n = sc.nextInt(), p = primeSet.ceiling(n);
		
		while(primeSet.contains(p - n + 1))
			p = primeSet.higher(p);
		
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(i == j)
					pw.print(+(p - n + 1)+" ");
				else
					pw.print(+1+" ");
			}
			pw.println();
		}
    }
}