There is a pyramid which consists of $n$ floors. The floors are numbered from top to bottom in increasing order. In the pyramid, the $i$-th floor consists of $i$ rooms.

Denote the $j$-th room on the $i$-th floor as $(i,j)$. For all positive integers $i$ and $j$ such that $1 \le j \le i < n$, there are $2$ one-way staircases which lead from $(i,j)$ to $(i+1,j)$ and from $(i,j)$ to $(i+1,j+1)$ respectively.

In each room you can either put a torch or leave it empty. Define the brightness of a room $(i, j)$ to be the number of rooms with a torch from which you can reach the room $(i, j)$ through a non-negative number of staircases.

For example, when $n=5$ and torches are placed in the rooms $(1,1)$, $(2,1)$, $(3,2)$, $(4,1)$, $(4,3)$, and $(5,3)$, the pyramid can be illustrated as follows:

In the above picture, rooms with torches are colored in yellow, and empty rooms are white. The blue numbers in the bottom-right corner indicate the brightness of the rooms.

The room $(4,2)$ (the room with a star) has brightness $3$. In the picture below, the rooms from where you can reach $(4,2)$ have red border. The brightness is $3$ since there are three torches among these rooms.

The pyramid is called nice if and only if for all floors, all rooms in the floor have the same brightness.

Define the brilliance of a nice pyramid to be the sum of brightness over the rooms $(1,1)$, $(2,1)$, $(3,1)$, ..., $(n,1)$.

Find an arrangement of torches in the pyramid, such that the resulting pyramid is nice and its brilliance is maximized.

We can show that an answer always exists. If there are multiple answers, output any one of them.


-----Input-----

The first line of the input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains a single positive integer $n$ ($1 \le n \le 500$) — the number of floors in the pyramid.

It is guaranteed that the sum of $n$ over all test cases does not exceed $500$.


-----Output-----

For each test case, output $n$ lines, the arrangement of torches in the pyramid.

The $i$-th line should contain $i$ integers, each separated with a space. The $j$-th integer on the $i$-th line should be $1$ if room $(i,j)$ has a torch, and $0$ otherwise.

We can show that an answer always exists. If there are multiple answers, output any one of them.


-----Examples-----

Input
3
1
2
3
Output
1 
1 
1 1 
1 
1 1 
1 0 1


-----Note-----

In the third test case, torches are placed in $(1,1)$, $(2,1)$, $(2,2)$, $(3,1)$, and $(3,3)$.

The pyramid is nice as rooms on each floor have the same brightness. For example, all rooms on the third floor have brightness $3$.

The brilliance of the pyramid is $1+2+3 = 6$. It can be shown that no arrangements with $n=3$ will have a greater brilliance.

Difficulty: EASY
Tags: Constructive algorithms

Starter code:

Solutions:
n = int(input())
for p in range(n):
	l = int(input())
	for i in range(l):
		if i == 0:
			print('1')
		else:
			print('1 ' + '0 ' * (i - 1) + '1')


for n in [*map(int, open(0))][1:]:
	print(1, *('1 ' + '0 ' * i + '1 ' for i in range(n - 1)))


for _ in range(int(input())):
	nn = int(input())
	print('1')
	for i in range(2, nn + 1):
		print('1' + ' 0' * (i - 2) + ' 1')


for _ in range(int(input())):
	n = int(input())
	print('1')
	for i in range(2, n + 1):
		print('1' + ' 0' * (i - 2) + ' 1')


for case in range(int(input())):
	num = int(input())
	for f in range(1, num + 1):
		if f == 1:
			print('1')
		elif f == 2:
			print('1 1')
		else:
			print('1 ' + '0 ' * (f - 2) + '1')


import sys

def run():
	n = int(sys.stdin.readline().strip())
	print(1)
	for i in range(2, n + 1):
		lanterns = ['1'] + ['0'] * (i - 2) + ['1']
		print(' '.join(lanterns))
t = int(input())
for _ in range(t):
	run()


for i in range(int(input())):
	for i in range(int(input())):
		if i == 0:
			print('1')
		elif i == 1:
			print('1 1')
		else:
			print('1 ' + '0 ' * (i - 1) + '1')


for i in range(int(input())):
	leng = int(input())
	for i in range(1, leng + 1):
		if i != 1:
			print(' '.join([str(1)] + [str(0)] * (i - 2) + [str(1)]))
		else:
			print(1)


def PP(n):
	print(1)
	if n > 1:
		for i in range(n - 1):
			l = ['1'] + ['0' for x in range(i)] + ['1']
			print(' '.join(l))
t = int(input())
for i in range(t):
	n = int(input())
	PP(n)


t = int(input())
for t1 in range(t):
	n = int(input())
	for i in range(1, n + 1):
		if i <= 2:
			print(' '.join(['1'] * i))
		else:
			print('1 ' + ' '.join(['0'] * (i - 2)) + ' 1')


t = int(input())
for q in range(t):
	n = int(input())
	for i in range(1, n + 1):
		if i == 1:
			print(1)
			continue
		print('1 ' + '0 ' * (i - 2) + '1')


k = int(input())
for l in range(k):
	item = int(input())
	if item == 1:
		print('1')
	elif item == 2:
		print('1')
		print('1 1')
	else:
		print('1')
		print('1 1')
		for x in range(1, item - 1):
			string = '1 ' + ' '.join(['0'] * x) + ' 1'
			print(string)


for _ in range(int(input())):
	vmp_n = int(input())
	print('1')
	for qwds in range(2, vmp_n + 1):
		print('1' + ' 0' * (qwds - 2) + ' 1')
		continue


t = int(input())

def printModule(n: int):
	if n == 1:
		print(1)
		return
	st = '1'
	st += ' 0' * (n - 2)
	st += ' 1'
	print(st)
for _ in range(t):
	n = int(input())
	for i in range(1, n + 1):
		printModule(i)


def solve():
	t = int(input())
	result = []
	for _ in range(t):
		n = int(input())
		pyramid = ['1']
		if n == 1:
			result.append(pyramid)
			continue
		for i in range(1, n):
			pyramid.append('1' + ' 0' * (i - 1) + ' 1')
		result.append(pyramid)
	return result
result = solve()
for pyramid in result:
	[print(floor) for floor in pyramid]


import sys
from collections import defaultdict
sys.setrecursionlimit(1 << 30)

def listInput():
	return list(map(int, input().split()))

def integerInput():
	return int(input())

def stringInput():
	return list(input())

def solve(array):
	array.sort()
	res = float('inf')
	n = len(array)
	for i in range(1, n - 1):
		left = array[i] - array[i - 1]
		right = array[i + 1] - array[i]
		res = min(res, left + right)
	return res
for _ in range(integerInput()):
	n = integerInput()
	print('1')
	if n == 1:
		continue
	print('1 1')
	for i in range(3, n + 1):
		zeros = '0 ' * (i - 2)
		print('1 ' + zeros + '1')


t = int(input())
for testcase in range(t):
	n = int(input())
	for i in range(n):
		line = '1 '
		if i > 1:
			line += '0 ' * (i - 1) + '1'
		elif i == 1:
			line += '1'
		print(line)


t = int(input())
for i in range(t):
	n = int(input())
	for i in range(1, n + 1):
		ans = ['0'] * i
		ans[0] = '1'
		ans[-1] = '1'
		print(' '.join(ans))


t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print('1')
		continue
	print('1')
	for i in range(2, n + 1):
		print('1', end=' ')
		if i - 2 > 0:
			print('0 ' * (i - 2), end='')
		print('1')


t = int(input())
for i in range(t):
	n = int(input())
	for j in range(1, n + 1):
		if j == 1:
			print('1')
		elif j == 2:
			print('1 ' + '1')
		else:
			print('1 ' + '0 ' * (j - 2) + '1')


for a in range(int(input())):
	n = int(input())
	for b in range(1, n + 1):
		if b == 1:
			print('1 ')
		else:
			print('1 ' + '0 ' * (b - 2) + '1 ')


n = int(input())
for i in range(n):
	l = int(input())
	lst = []
	for j in range(1, l + 1):
		temp = ['0'] * j
		lst.append(temp)
	for m in range(len(lst)):
		lst[m][0] = '1'
		lst[m][-1] = '1'
	for m in lst:
		print(' '.join(m))


t = int(input())
for tc in range(t):
	n = int(input())
	for i in range(n):
		if i == 0:
			print(str(1))
		elif i == 1:
			print(str('1 1'))
		else:
			print(str(1) + str(' 0') * (i - 1) + str(' ') + str(1))


t = int(input())
for i in range(t):
	n = int(input())
	print('1')
	for i in range(2, n + 1):
		print('1' + ' 0' * (i - 2) + ' 1')


import itertools
import math
import sys
for _ in range(int(input())):
	num = int(input())
	for i in range(1, num + 1):
		if i == 1:
			print('1')
			continue
		if i == 2:
			print('1 1')
			continue
		else:
			print('1 ', end='')
			print('0 ' * (i - 2), end='')
			print('1')


def solve():
	n = int(input())
	ans = ['1']
	for i in range(2, n + 1):
		e = ['1'] + ['0'] * (i - 2) + ['1']
		ans.append(' '.join(e))
	return '\n'.join(ans)
t = int(input())
ans = []
while t:
	ans.append(str(solve()))
	t -= 1
print('\n'.join(ans))


for _ in range(int(input())):
	hemanth = int(input())
	print('1')
	for ka in range(2, hemanth + 1):
		print('1' + ' 0' * (ka - 2) + ' 1')


def solution(n):
	for i in range(n):
		if i == 0:
			print(1)
		elif i == 1:
			print(1, 1)
		else:
			s = '1 '
			s += '0 ' * (i - 1)
			s += '1'
			print(s)
t = int(input())
while t:
	n = int(input())
	solution(n)
	t -= 1


for _ in range(int(input())):
	x = int(input())
	for i in range(1, x + 1):
		p = ''
		if i == 1:
			p += '1'
		else:
			p += '1 '
			p += '0 ' * (i - 2)
			p += '1'
		print(p)


for nbd in [*map(int, open(0))][1:]:
	print(1, *('1 ' + '0 ' * i + '1 ' for i in range(nbd - 1)))


for _ in range(int(input())):
	n = int(input())
	print('1')
	for x in range(1, n):
		print('1' + ' 0' * (x - 1) + ' 1')


for _ in range(int(input())):
	nnn = int(input())
	print('1')
	for i in range(2, nnn + 1):
		print('1' + ' 0' * (i - 2) + ' 1')


def brighter_rooms(floors):
	for i in range(1, floors + 1):
		if i <= 2:
			print('1 ' * i)
		else:
			temp = '0 ' * (i - 2)
			temp = '1 ' + temp
			temp += '1'
			print(temp)
int_input = int(input())
for i in range(int_input):
	floors = int(input())
	brighter_rooms(floors)


for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(1)
		print(1, 1)
	else:
		print(1)
		print(1, 1)
		j = 0
		while j < n - 2:
			print(1, end=' ')
			print('0 ' * (j + 1), end='')
			print(1)
			j += 1


test_cases = int(input())
for case in range(test_cases):
	floors = int(input())
	if floors <= 2:
		for i in range(1, floors + 1):
			print(('1 ' * i)[:-1])
	else:
		for i in range(1, 3):
			print(('1 ' * i)[:-1])
		for i in range(3, floors + 1):
			print('1 ' + ('0 ' * (i - 2))[:-1] + ' 1')


for _ in range(int(input())):
	n = int(input())
	for i in range(n):
		if i == 0:
			print('1')
		else:
			l = list('1' + '0' * (i + 1 - 2) + '1')
			print(' '.join(l))


for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(1)
		print(1, 1)
	else:
		print(1)
		print(1, 1)
		c = 1
		for i in range(1, n - 1):
			print(1, '0 ' * i + str(1))


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print('1')
		continue
	if n == 2:
		print('1')
		print('1 1')
		continue
	else:
		out = ['1', '1 1']
		for x in range(3, n + 1):
			tmp_s = ' '.join(['0' for z in range(x - 2)])
			out.append('1 ' + tmp_s + ' 1')
		for x in out:
			print(x)


n = int(input())

def help(x):
	ans = '1'
	if x == 1:
		return ans
	for i in range(2, x + 1):
		ans2 = '1'
		for j in range(i - 2):
			ans2 += ' 0'
		ans2 += ' 1'
		ans = ans + '\n' + ans2
	return ans
output = []
for i in range(n):
	x = int(input())
	output.append(help(x))
for out in output:
	print(out)


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	for i in range(n):
		if i == 0:
			print(1)
			continue
		re = '1 ' + '0 ' * (i + 1 - 2) + '1'
		print(re)


for p in [*map(int, open(0))][1:]:
	print(1, *('1 ' + '0 ' * j + '1 ' for j in range(p - 1)))


for W in [*map(int, open(0))][1:]:
	print(1, *('1 ' + '0 ' * i + '1 ' for i in range(W - 1)))


for N in [*map(int, open(0))][1:]:
	print(1, *('1 ' + '0 ' * j + '1 ' for j in range(N - 1)))


for inp_n in [*map(int, open(0))][1:]:
	print(1, *('1 ' + '0 ' * i + '1 ' for i in range(inp_n - 1)))


for nbr in [*map(int, open(0))][1:]:
	print(1, *('1 ' + '0 ' * i + '1 ' for i in range(nbr - 1)))


for nice in [*map(int, open(0))][1:]:
	print(1, *('1 ' + '0 ' * itadori + '1 ' for itadori in range(nice - 1)))


t = int(input())
for _ in range(t):
	n = int(input())
	for i in range(1, n + 1):
		print(' '.join(['1' if x == 0 or x == i - 1 else '0' for x in range(i)]))


for name in [*map(int, open(0))][1:]:
	print(1, *('1 ' + '0 ' * i + '1 ' for i in range(name - 1)))


t = int(input())
for _ in range(t):
	n = int(input())
	for i in range(n):
		if i == 0:
			print('1')
		elif i == 1:
			print('1 1')
		else:
			print(f"1 {'0 ' * (i - 1)}1")


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print('1')
		continue
	print('1')
	print('1 1')
	for i in range(1, n - 1):
		s = '1'
		for j in range(i):
			s += ' 0'
		s += ' 1'
		print(s)


import sys
import threading
from functools import lru_cache

def main():
	T = int(input())
	for _ in range(T):
		n = int(input())
		for i in range(n):
			arr = ['0'] * (i + 1)
			arr[0] = '1'
			arr[-1] = '1'
			print(' '.join(arr))
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()


t = int(input())
for ind in range(t):
	n = int(input())
	print('1')
	for i in range(1, n):
		print('1 ' + (i - 1) * '0 ' + '1')


t = int(input())
while t > 0:
	n = int(input())
	for i in range(n):
		s = ['0' for i in range(i + 1)]
		s[0] = '1'
		s[-1] = '1'
		print(' '.join(s))
	t -= 1


def solve():
	n = int(input())
	a = []
	i = 1
	tem = ['0']
	while i <= n:
		x = tem * i
		if len(x) == 1:
			x[0] = 1
		elif len(x) == 2:
			(x[0], x[1]) = [1, 1]
		else:
			(x[0], x[-1]) = (1, 1)
		a.append(x)
		i += 1
	for i in a:
		print(' '.join((str(ini) for ini in i)))
for t in range(0, int(input())):
	solve()


t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print('1')
	else:
		print('1')
		for i in range(1, n):
			mylist = []
			mylist.append(1)
			for j in range(1, i):
				mylist.append(0)
			mylist.append(1)
			print(' '.join(map(str, mylist)))