Rashmi loves the festival of Diwali as she gets to spend time with family and enjoy the festival. Before she can fully enjoy the festival she needs to complete the homework assigned by her teacher. Since Rashmi is smart , she has solved all the problems but is struck at one tricky pattern question.
Your Task is to help Rashmi solve the problem so that she can enjoy the festival with her family.
The Problem she is struck on is defined like this:
Given an integer N you need to generate the pattern according to following example:
Example:

Input:

3  
Output:

1 4 10

2 5 11

4 10 22

3 6 12  

-----Input:-----
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The next line of each contains T space separated integers N.

-----Output:-----
For each N print the required pattern.

-----Constraints:-----
$1 \leq T \leq 10^5$
$1 \leq N \leq 30$

-----Sample Input:-----
2
3 5

-----Sample Output:-----
1 4 10

2 5 11

4 10 22

3 6 12

1 4 10 22 46

2 5 11 23 47

4 10 22 46 94

3 6 12 24 48  

-----Sample Input:-----
1

4  

-----Sample Output:-----
1 4 10 22

2 5 11 23

4 10 22 46

3 6 12 24

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
a = int(input())
p = list(map(int, input().split()))
for n in p:
	a = [1]
	b = [2]
	c = [4]
	d = [3]
	j = 1
	k = 1
	for i in range(n - 1):
		a.append(a[i] + 3 * j)
		b.append(b[i] + 3 * j)
		c.append(c[i] + 6 * j)
		d.append(d[i] + 3 * j)
		j *= 2
	print(*a)
	print(*b)
	print(*c)
	print(*d)


t = int(input())
nlist = [int(x) for x in input().split(' ') if x != '']
nums = [1, 2, 4, 3]
add = 3
for flag in range(t):
	n = nlist[flag]
	for num in nums:
		x = num
		for a in range(n):
			print(x, end=' ')
			if num == 4:
				x = x + add * pow(2, a + 1)
			else:
				x = x + add * pow(2, a)
		print('')


def first_row(n):
	l = [1]
	s = [2]
	t = [4]
	f = [3]
	d = 3
	for i in range(n - 1):
		l.append(l[-1] + d)
		s.append(l[-1] + 1)
		t.append(s[-1] * 2)
		f.append(s[-1] + 1)
		d = d * 2
	for i in range(len(l)):
		print(l[i], end=' ')
	print('')
	for i in range(len(s)):
		print(s[i], end=' ')
	print('')
	for i in range(len(t)):
		print(t[i], end=' ')
	print('')
	for i in range(len(f)):
		print(f[i], end=' ')
	print('')
t = int(input())
l = list(map(int, input().split()))
for i in range(len(l)):
	first_row(l[i])


t = 0
try:
	t = int(input())
except:
	pass
for _ in range(t):
	try:
		l = list(map(int, input().split()))
	except:
		pass
for n in l:
	if n in range(1, 31):
		(a, b, c, d) = (1, 2, 4, 3)
		print('1', end=' ')
		for _ in range(n - 1):
			a = (a + 1) * 2
			print(a, end=' ')
		print('')
		print('2', end=' ')
		for _ in range(n - 1):
			b = b * 2 + 1
			print(b, end=' ')
		print('')
		print('4', end=' ')
		for _ in range(n - 1):
			c = c * 2 + 2
			print(c, end=' ')
		print('')
		print('3', end=' ')
		for _ in range(n - 1):
			d = d * 2
			print(d, end=' ')
		print('')


t = int(input())
ar = list(map(int, input().split()))
for i in ar:
	z = 3
	a = 1
	for j in range(i):
		print(str(a), end=' ')
		a = a + z
		z = 2 * z
	print('\r')
	z = 3
	a = 2
	for j in range(i):
		print(str(a), end=' ')
		a = a + z
		z = 2 * z
	print('\r')
	z = 6
	a = 4
	for j in range(i):
		print(str(a), end=' ')
		a = a + z
		z = 2 * z
	print('\r')
	z = 3
	a = 3
	for j in range(i):
		print(str(a), end=' ')
		a = a + z
		z = 2 * z
	print('\r')


n = int(input())
a = [int(i) for i in input().split()]
for av in a:
	temp = []
	temp.append(1)
	for j in range(av - 1):
		temp.append(3 * 2 ** j + temp[-1])
	for v in temp:
		print(v, end=' ')
	print('\n', end='')
	temp1 = [i + 1 for i in temp]
	for v in temp1:
		print(v, end=' ')
	print('\n', end='')
	temp2 = [2 * i for i in temp1]
	for v in temp2:
		print(v, end=' ')
	print('\n', end='')
	dummy = []
	for k in range(len(temp)):
		dummy.append(temp2[k] - temp[k])
	for v in dummy:
		print(v, end=' ')
	print('\n', end='')


totIts = int(input())
colCts = list(map(int, input().split()))
for i in range(totIts):
	currColCt = colCts[i]
	for j in [1, 2, 4, 3]:
		c = j
		if c != 4:
			print(c, end=' ')
			for k in range(0, currColCt - 1):
				res = c + 3 * 2 ** k
				print(res, end=' ')
				c = res
		else:
			print(c, end=' ')
			for k in range(0, currColCt - 1):
				res = c + 6 * 2 ** k
				print(res, end=' ')
				c = res
		print('')


t = int(input())
nums = list(map(int, input().split()))
for i in nums:
	for row in range(1, 5):
		if row == 3:
			y = row + 1
			x = 3 * 2
		elif row == 4:
			y = row - 1
			x = 3
		else:
			y = row
			x = 3
		for col in range(1, i + 1):
			print(y, end=' ')
			y += x
			x *= 2
		print()


l = [1]
for i in range(32):
	l.append(l[-1] + 3 * 2 ** i)
m = []
for i in range(33):
	m.append(l[i] + 1)
n = []
for i in range(33):
	n.append(m[i] * 2)
o = []
for i in range(33):
	o.append(m[i] + 1)
t = int(input())
inp = [int(i) for i in input().split()]
for j in range(t):
	y = inp[j]
	for i in range(y):
		print(l[i], end=' ')
	print()
	for i in range(y):
		print(m[i], end=' ')
	print()
	for i in range(y):
		print(n[i], end=' ')
	print()
	for i in range(y):
		print(o[i], end=' ')
	print()


try:
	t = int(input())
	mlist = list(map(int, input().split()))
	for i in range(0, len(mlist)):
		slist = [[1], [2], [4], [3]]
		for j in range(0, len(slist)):
			for k in range(0, mlist[i] - 1):
				if j == 0:
					slist[0].append(slist[0][-1] * 2 + 2)
				if j == 1:
					slist[1].append(slist[1][-1] * 2 + 1)
				if j == 2:
					slist[2].append(slist[2][-1] * 2 + 2)
				if j == 3:
					slist[3].append(slist[3][-1] * 2)
		for j in range(0, len(slist)):
			for k in range(0, len(slist[j])):
				print(slist[j][k], end=' ')
			print()
except:
	pass


n = int(input())
ns = list(map(int, input().split()))
for i in range(n):
	lst = [[1], [2], [4], [3]]
	for j in range(1, ns[i]):
		lst[0].append(lst[0][j - 1] * 2 + 2)
		lst[1].append(lst[1][j - 1] * 2 + 1)
		lst[2].append(lst[2][j - 1] * 2 + 2)
		lst[3].append(lst[3][j - 1] * 2)
	for k in range(4):
		for p in range(len(lst[0])):
			print(lst[k][p], end=' ')
		print()


t = int(input())
ns = list(map(int, input().split()))
for n in ns:
	a = [[1], [2], [4], [3]]
	for i in range(n - 1):
		d = a[0][-1] * 2 + 2
		a[0].append(d)
		d = a[1][-1] * 2 + 1
		a[1].append(d)
		d = a[2][-1] * 2 + 2
		a[2].append(d)
		d = a[3][-1] * 2
		a[3].append(d)
	for i in a:
		for j in i:
			print(j, end=' ')
		print()


def op(n):
	m = 3
	l = [[1], [2], [4], [3]]
	for _ in range(n - 1):
		for row in l:
			if row == l[2]:
				row.append(row[-1] + 2 * m)
			else:
				row.append(row[-1] + m)
		m = m * 2
	for row in l:
		for elem in row:
			print(elem, end=' ')
		print('\n')
t = int(input())
ns = list(map(int, input().split()))
for n in ns:
	op(n)


t = int(input())
list1 = []
arr = list(map(int, input().split()))
for i in range(t):
	for j in range(4):
		if j == 0:
			list1.append(1)
			print(list1[-1], end=' ')
			for x in range(1, arr[i]):
				list1.append(list1[-1] * 2 + 2)
				print(list1[-1], end=' ')
			print()
		elif j == 1:
			list1.append(2)
			print(list1[-1], end=' ')
			for x in range(1, arr[i]):
				list1.append(list1[-1] * 2 + 1)
				print(list1[-1], end=' ')
			print()
		elif j == 2:
			list1.append(4)
			print(list1[-1], end=' ')
			for x in range(1, arr[i]):
				list1.append(list1[-1] * 2 + 2)
				print(list1[-1], end=' ')
			print()
		elif j == 3:
			list1.append(3)
			print(list1[-1], end=' ')
			for x in range(1, arr[i]):
				list1.append(list1[-1] * 2)
				print(list1[-1], end=' ')
			print()


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100000000)
ii = lambda : int(input())
si = lambda : input()
jn = lambda x, l: x.join(map(str, l))
sl = lambda : list(map(str, input().strip()))
mi = lambda : map(int, input().split())
mif = lambda : map(float, input().split())
lii = lambda : list(map(int, input().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 1000000007
n = ii()
arr = lii()
for i in range(n):
	for j in range(4):
		if j == 0:
			val = 1
		elif j == 1:
			val = 2
		elif j == 2:
			val = 4
		elif j == 3:
			val = 3
		for k in range(arr[i]):
			ans = 0
			if k > 0:
				ans = 2 ** (k - 1)
			if j == 3:
				val += 3 * ans
				print(val, end=' ')
			elif j == 0 or j == 1:
				val += 3 * ans
				print(val, end=' ')
			else:
				val += 6 * ans
				print(val, end=' ')
		print()


t = int(input())
l = list(map(int, input().split()))
for i in range(t):
	a = 1
	k = 3
	for j in range(l[i]):
		print(a, end=' ')
		a = a + k
		k = k + k
	print()
	a = 2
	k = 3
	for j in range(l[i]):
		print(a, end=' ')
		a = a + k
		k = k + k
	print()
	a = 4
	k = 6
	for j in range(l[i]):
		print(a, end=' ')
		a = a + k
		k = k + k
	print()
	a = 3
	k = 3
	for j in range(l[i]):
		print(a, end=' ')
		a = a + k
		k = k + k
	print()


T = int(input())
n = list(map(int, input().split()))
for i in n:
	l1 = [1]
	l2 = [2]
	l3 = [4]
	l4 = [3]
	for t in range(1, i):
		l1.append(l1[-1] + 3 * 2 ** (t - 1))
		l2.append(l1[-1] + 1)
		l3.append(l3[-1] + 6 * 2 ** (t - 1))
		l4.append(l4[-1] * 2)
	l1 = list(map(str, l1))
	l2 = list(map(str, l2))
	l3 = list(map(str, l3))
	l4 = list(map(str, l4))
	print(' '.join(l1))
	print(' '.join(l2))
	print(' '.join(l3))
	print(' '.join(l4))


def pattern(n):
	first = [0] * n
	second = [0] * n
	third = [0] * n
	forth = [0] * n
	first[0] = 1
	second[0] = 2
	third[0] = 4
	forth[0] = 3
	if n > 1:
		for i in range(1, n):
			first[i] = first[i - 1] + second[i - 1] + 1
			second[i] = first[i - 1] + second[i - 1] + 2
			third[i] = second[i] * 2
			forth[i] = second[i] + 1
	for a in first:
		print(a, end=' ')
	print('')
	for b in second:
		print(b, end=' ')
	print('')
	for c in third:
		print(c, end=' ')
	print('')
	for d in forth:
		print(d, end=' ')
	print('')
T = int(input())
N = list(map(int, input().split()))
for n in N:
	pattern(n)


def print_pattern(n):
	a = [1]
	b = []
	c = []
	d = []
	for i in range(n):
		if i != 0:
			a.append((a[i - 1] + 1) * 2)
	for i in range(n):
		b.append(a[i] + 1)
	for i in range(n - 1):
		c.append(a[i + 1])
	c.append((a[n - 1] + 1) * 2)
	for i in range(n):
		d.append(a[i] + 2)
	for i in range(n):
		print(a[i], end=' ')
	print()
	for i in range(n):
		print(b[i], end=' ')
	print()
	for i in range(n):
		print(c[i], end=' ')
	print()
	for i in range(n):
		print(d[i], end=' ')
	print()
	return
t = int(input())
n = [int(x) for x in input().split()]
for i in n:
	m = print_pattern(int(i))


t = int(input())
n = list(map(int, input().split()[:t]))
for i in n:
	li = [3]
	li1 = 3
	list1 = [1]
	list2 = [2]
	list3 = [4]
	list4 = [3]
	l1 = 1
	l2 = 2
	l3 = 4
	l4 = 3
	for j in range(i - 1):
		li.append(li1 * 2)
		li1 = li1 * 2
	for i in range(i - 1):
		list1.append(l1 + li[i])
		l1 = l1 + li[i]
		list2.append(l2 + li[i])
		l2 = l2 + li[i]
		list3.append(l3 + li[i + 1])
		l3 = l3 + li[i + 1]
		list4.append(l4 + li[i])
		l4 = l4 + li[i]
	for i in list1:
		print(i, end=' ')
	print()
	for i in list2:
		print(i, end=' ')
	print()
	for i in list3:
		print(i, end=' ')
	print()
	for i in list4:
		print(i, end=' ')
	print()


t = int(input())
lst = list(map(int, input().split()))
for _ in range(len(lst)):
	n = lst[_]
	l = [[0] * n, [0] * n, [0] * n, [0] * n]
	c = 1
	for i in range(n):
		for j in range(4):
			if j == 2:
				continue
			else:
				l[j][i] = c
				c += 1
		l[2][i] = l[3][i] + l[0][i]
		c = l[2][i]
	for i in range(4):
		for j in range(n):
			if j != 3:
				print(l[i][j], end=' ')
			else:
				print(l[i][j], end=' ')
		print()