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

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

public class cf_subs {
	static FastReader scn = new FastReader();
	static OutputStream out = new BufferedOutputStream(System.out);
	@SuppressWarnings("unchecked")
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		boolean[] sieve = new boolean[100001];
		Arrays.fill(sieve, true);
		sieve[0]=sieve[1]=false;
		for(int i=2;i<sieve.length;i++) {
			if(sieve[i]) {
				for(int j=2*i;j<sieve.length;j+=i) {
					sieve[j]=false;
				}
			}
		}
		ArrayList<Integer> primes = new ArrayList<>();
		for(int i=2;i<sieve.length;i++) {
			if(sieve[i]) {
				primes.add(i);
			}
		}
		int tc = scn.nextInt();
//		int tc = 1;
//		Here:
		while(tc-->0) {
			int n =scn.nextInt();
			if(sieve[n]) {
				for(int i=0;i<n;i++) {
					for(int j=0;j<n;j++) {
						out.write("1 ".getBytes());
					}
					out.write("\n".getBytes());
				}
				continue;
			}
			int ub = upperBound(primes,n);
			int diff= -1;
			for(int i=ub;i<primes.size();i++) {
//				int here = primes.get(i)-n+1;
				if(!sieve[primes.get(i)-n+1]) {
					diff = primes.get(i)-n+1;
					break;
				}
			}
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					if(i==j) {
						out.write((diff+" ").getBytes());
					}else {
						out.write("1 ".getBytes());
					}
				}
				out.write("\n".getBytes());
			}
		}
		out.close();
	}
	static long div_gint(long n, long x) {
		if(n%x==0) {
			return n/x;
		}
		return n/x+1;
	}
//	static long binexp(long x, long p) {
//		long ans=1;
//		long cur = x;
//		while(p>0) {
//			if((p&1)==1) {
//				ans = ((ans%MOD)*(cur%MOD))%MOD;
//			}
//			cur =(cur*cur)%MOD;
//			p=p>>1;
//		}
//		return ans%MOD;
//	}
	static long gcd(long a, long b) {
		if(a==0)
			return b;
		return gcd(b%a,a);
	}
	static class Edge implements Comparable<Edge>{
		int u,v,w;
		public Edge(int u, int v, int w) {
			this.u=u;this.v =v;this.w =w;
		}
		public int compareTo(Edge o) {
			return this.w-o.w;
		}
		public String toString() {
			return "["+u+','+v+','+w+']';
		}
	}
//	static class Pair implements Comparable<Pair>{
//		int first;
//		int second;
//		int idx;
//		public Pair() {
//			this.first=-1;
//			this.second =-1;
//			this.idx=-1;
//		}
//		public Pair(int first) {
//			this.first = first;
//			this.second =-1;
//			this.idx=-1;
//		}
//		public Pair(int first, int second,int idx) {
//			this.first = first;
//			this.second = second;
//			this.idx=idx;
//		}
//		public int compareTo(Pair o) {
//			return this.first+this.second-o.first-o.second;
//		}
//		public String toString() {
//			return "{"+this.first+","+this.second+"}";
//		}
//	}
	static class Pair<S extends Comparable<S>,T extends Comparable<T>> implements Comparable<Pair<S,T>>{
		S first;
		T second;
//		int idx;
		public Pair() {
			this.first=null;
			this.second =null;
//			this.idx=-1;
		}
		public Pair(S first) {
			this.first = first;
			this.second =null;
//			this.idx=-1;
		}
		public Pair(S first, T second) {
			this.first = first;
			this.second = second;
//			this.idx=idx;
		}
		public int compareTo(Pair<S,T> o) {
			if(this.first.compareTo(o.first)==0) {
				return this.second.compareTo(o.second);
			}
			return this.first.compareTo(o.first);
		}
		public String toString() {
			return "{"+this.first.toString()+","+this.second.toString()+"}";
		}
	}
	static int log(long N) {
		// TODO Auto-generated method stub
		return 63- Long.numberOfLeadingZeros(N);
	}
	static int lowerBound(int[] a, int x,int lf,int rg) {
		int l = lf-1, r = rg+1;
		while (r - l > 1) {
			int c = (l + r) / 2;
			if (a[c] < x) {
				//if (a[c] > x) {
				l = c;
			} else {
				r = c;
			}
		}
		return r;
	}
	static int upperBound(int[] a, int x,int lf,int rg) {
		int l = lf-1, r = rg+1;
		while (r - l > 1) {
			int c = (l + r) / 2;
			if (a[c] <= x) {
				l = c;
			} else {
				r = c;
			}
		}
		return r;
	}
 
	static int lowerBound(long[] a, long x) {
		int l = -1, r = a.length;
		while (r - l > 1) {
			int c = (l + r) / 2;
			if (a[c] < x) {
				l = c;
			} else {
				r = c;
			}
		}
		return r;
	}
 
	static int upperBound(long[] a, long x) {
		int l = -1, r = a.length;
		while (r - l > 1) {
			int c = (l + r) / 2;
			if (a[c] <= x) {
				l = c;
			} else {
				r = c;
			}
		}
		return r;
	}
 
	static int lowerBound(double[] a, double x) {
		int l = -1, r = a.length;
		while (r - l > 1) {
			int c = (l + r) / 2;
			if (a[c] < x) {
				l = c;
			} else {
				r = c;
			}
		}
		return r;
	}
 
	static int upperBound(double[] a, double x) {
		int l = -1, r = a.length;
		while (r - l > 1) {
			int c = (l + r) / 2;
			if (a[c] <= x) {
				l = c;
			} else {
				r = c;
			}
		}
		return r;
	}
 
	@SuppressWarnings("unchecked")
	static <T> int lowerBound(List<T> ls, T x) throws RuntimeException {
		if (ls.size() == 0)
			return -1;
		if (ls.get(0) instanceof Integer) {
			return ~Collections.binarySearch(ls, x, (t1, t2) -> ((Integer) t1).compareTo((Integer) t2) >= 0 ? 1 : -1);
		} else if (ls.get(0) instanceof Long) {
			return ~Collections.binarySearch(ls, x, (t1, t2) -> ((Long) t1).compareTo((Long) t2) >= 0 ? 1 : -1);
		} else if (ls.get(0) instanceof Double) {
			return ~Collections.binarySearch(ls, x, (t1, t2) -> ((Double) t1).compareTo((Double) t2) >= 0 ? 1 : -1);
		} else if(ls.get(0) instanceof Pair){
			return ~Collections.binarySearch(ls, x,(t1,t2)->(((Pair<Integer,Integer>) t1).compareTo((Pair<Integer,Integer>)t2)>=0?1:-1));
		}else{
			System.err.println(
					String.format("%s:Arey Maa chudi padi hai", Thread.currentThread().getStackTrace()[1].getMethodName()));
			throw new RuntimeException();
		}
	}
 
	static <T> int upperBound(List<T> ls, T x) throws RuntimeException {
		if (ls.size() == 0)
			return -1;
		if (ls.get(0) instanceof Integer) {
			return ~Collections.binarySearch(ls, x, (t1, t2) -> ((Integer) t1).compareTo((Integer) t2) > 0 ? 1 : -1);
		} else if (ls.get(0) instanceof Long) {
			return ~Collections.binarySearch(ls, x, (t1, t2) -> ((Long) t1).compareTo((Long) t2) > 0 ? 1 : -1);
		} else if (ls.get(0) instanceof Double) {
			return ~Collections.binarySearch(ls, x, (t1, t2) -> ((Double) t1).compareTo((Double) t2) > 0 ? 1 : -1);
		} else {
			System.err.println(
					String.format("%s:Arey Maa chudi padi hai", Thread.currentThread().getStackTrace()[1].getMethodName()));
			throw new RuntimeException();
		}
	}
 
	static <T> int rupperBound(List<T> ls, T x) throws RuntimeException {
		if (ls.size() == 0)
			return -1;
		if (ls.get(0) instanceof Integer) {
			return ~Collections.binarySearch(ls, x, (t1, t2) -> ((Integer) t1).compareTo((Integer) t2) < 0 ? 1 : -1);
		} else if (ls.get(0) instanceof Long) {
			return ~Collections.binarySearch(ls, x, (t1, t2) -> ((Long) t1).compareTo((Long) t2) < 0 ? 1 : -1);
		} else if (ls.get(0) instanceof Double) {
			return ~Collections.binarySearch(ls, x, (t1, t2) -> ((Double) t1).compareTo((Double) t2) < 0 ? 1 : -1);
		} else {
			System.err.println(
					String.format("%s:Arey maa chudi padi hai", Thread.currentThread().getStackTrace()[1].getMethodName()));
			throw new RuntimeException();
		}
	}
 
	static <T> int rlowerBound(List<T> ls, T x) {
		if (ls.size() == 0)
			return -1;
		if (ls.get(0) instanceof Integer) {
			return ~Collections.binarySearch(ls, x, (t1, t2) -> ((Integer) t1).compareTo((Integer) t2) <= 0 ? 1 : -1);
		} else if (ls.get(0) instanceof Long) {
			return ~Collections.binarySearch(ls, x, (t1, t2) -> ((Long) t1).compareTo((Long) t2) <= 0 ? 1 : -1);
		} else if (ls.get(0) instanceof Double) {
			return ~Collections.binarySearch(ls, x, (t1, t2) -> ((Double) t1).compareTo((Double) t2) <= 0 ? 1 : -1);
		} else {
			System.err.println(
					String.format("%s:Arey maa chudi padi hai", Thread.currentThread().getStackTrace()[1].getMethodName()));
			throw new RuntimeException();
		}
	}
	public static int[] merge(int[] one,int[] two){
		int[] res = new int[one.length+two.length];
		int i = 0;
		int j = 0;
		int k = 0;
		
		while(i<one.length&&j<two.length){
			if(one[i]<two[j]){
				res[k] = one[i];
				i++;
				k++;
			}
			else{
				res[k] = two[j];
				j++;
				k++;
			}
		}
		
		if(i==one.length){
			while(j<two.length){
				res[k] = two[j];
				j++;
				k++;
			}
		}
		else{
			while(i<one.length){
				res[k] = one[i];
				k++;
				i++;
			}
		}
		return res;
	}
	public static int[] mergesort(int[] arr, int l, int r){
		if(l==r){
			int[] br = new int[1];
			br[0] = arr[l];
			return br;
		}
		int mid = (l+r)/2;
		int[] fh = mergesort(arr,l,mid);
		int[] sh = mergesort(arr,mid+1,r);
		
		return merge(fh,sh);
	}
	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()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }

}