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 PYTHON3):

Solution:
import sys
import math
import itertools
import functools
import collections
import operator
import fileinput
import copy
 
ORDA = 97  # a
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return [int(i) for i in input().split()]
def lcm(a, b): return abs(a * b) // math.gcd(a, b)
def revn(n): return str(n)[::-1]
def dd(): return collections.defaultdict(int)
def ddl(): return collections.defaultdict(list)
def sieve(n):
    if n < 2: return list()
    prime = [True for _ in range(n + 1)]
    p = 3
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 2
    r = [2]
    for p in range(3, n + 1, 2):
        if prime[p]:
            r.append(p)
    return r
def divs(n, start=2):
    r = []
    for i in range(start, int(math.sqrt(n) + 1)):
        if (n % i == 0):
            if (n / i == i):
                r.append(i)
            else:
                r.extend([i, n // i])
    return r
def divn(n, primes):
    divs_number = 1
    for i in primes:
        if n == 1:
            return divs_number
        t = 1
        while n % i == 0:
            t += 1
            n //= i
        divs_number *= t
def prime(n):
    if n == 2: return True
    if n % 2 == 0 or n <= 1: return False
    sqr = int(math.sqrt(n)) + 1
    for d in range(3, sqr, 2):
        if n % d == 0: return False
    return True
def convn(number, base):
    new_number = 0
    while number > 0:
        new_number += number % base
        number //= base
    return new_number
def cdiv(n, k): return n // k + (n % k != 0)
def ispal(s): # Palindrome
    for i in range(len(s) // 2 + 1):
        if s[i] != s[-i - 1]:
            return False
    return True
# a = [1,2,3,4,5] -----> print(*a) ----> list print krne ka new way

#rr = sieve(int(1000**0.5))
import math 

  
# Function that returns True if n  
# is prime else returns False  

def isPrime(n): 

      

    # Corner cases  

    if(n <= 1): 

        return False

    if(n <= 3): 

        return True

      

    # This is checked so that we can skip  

    # middle five numbers in below loop  

    if(n % 2 == 0 or n % 3 == 0): 

        return False

      

    for i in range(5,int(math.sqrt(n) + 1), 6):  

        if(n % i == 0 or n % (i + 2) == 0): 

            return False

      

    return True

  
# Function to return the smallest  
# prime number greater than N  

def nextPrime(N): 

  

    # Base case  

    if (N <= 1): 

        return 2

  

    prime = N 

    found = False

  

    # Loop continuously until isPrime returns  

    # True for a number greater than n  

    while(not found): 

        prime = prime + 1

  

        if(isPrime(prime) == True): 

            found = True

  

    return prime 
rr = sieve(500)
def main():
	r = rr
	for _ in range(ii()):
		n = ii()
		np = 4*(n-1)
		while np <= 1e5:
			#print(np)
			np = nextPrime(np)
			if not prime(np-4*(n-1)) and prime(4*(n-1) + (np - 4*(n-1))):
				break
		s =[4]*(n-1)
		np = (np -4*(n-1))
		for i in range(n):
			s.insert(i,np)
			print(*s)
			s.pop(i)
			
			#print(' '.join(s), str((np - 4*(n-1))))
		
main()