recursion

Problem :

Bajirao asks Avni out on a date. However, Avni will go out with him only on one condition : 

Bajirao has to tell her all possible N - digit numbers such that all the digits of every number he tells her are distinct , non-zero and   less than or equal to N. 

Also, he has to tell her all these numbers in ascending order. Help Bajirao so that he can take Avni out on a date.

Input

First line consists of T the number of test cases. The next T lines are such that each line consists of a single integer N.

Output

For every test case, print all the numbers Bajirao tells Avni, such that the numbers are in ascending order and every number is separated from the other by a single space. Print the answer to every test case on a new line.

Constraints :

1 ≤ T ≤ 3

1 ≤ N ≤ 9

Problem Setter : Shreyans

Problem Tester : Sandeep

(By IIT Kgp HackerEarth Programming Club)

SAMPLE INPUT
3
1
2
3

SAMPLE OUTPUT
1
12 21
123 132 213 231 312 321

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import itertools
def fun(k):
	l=[]
	for i in range(1,k+1):
		l.append(i)
	a=[]
	b=''
	for i in itertools.permutations(l,k):
		for j in i:
			b+=str(j)
		a.append(b)
		b=''
		
	a.sort(key=lambda x:int(x))
	print((' '.join(a)))
	#print(' '.join(a))
	
n=int(input())
for i in range(n):
	k=int(input())
	fun(k)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import itertools

#print 'Hello World!'
t=int(input())

for i in range (t):
	n=int(input())
	for j in itertools.permutations(list(range(1,n+1))):
		print((''.join(map(str,j))), end=' ')
	print(("\n"), end=' ')


import itertools
for _ in range(eval(input())):
	#x=input()
	#s=[]
	#for i in xrange(1,x+1):
		#s.append(i)
	#s1="".join(str(i) for i in s)
	#print s1
	for i in itertools.permutations(range(1,eval(input())+1)):
		print(''.join(map(str,i)), end=' ')
	print() 
	


import itertools

def main():
	t = int(input())
	al = '123456789'
	for test in range(t):
		n = int(input())
		pr = []
		perms = list(itertools.permutations(al[:n]))
		for tup in perms:
			tsum = ''
			for d in tup:
				tsum += d
			pr.append(int(tsum))
		pr.sort()
		print(' '.join(map(str, pr)))
		
if __name__ == '__main__':
	main()


def permutationG(input, s):
	if len(s) == len(input):
		print(s, end=' ')
		yield s
	for i in input:
		if i in s: continue
		s=s+i
		for x in permutationG(input, s): yield x
		s=s[:-1]

j = int(input())
while (j > 0):
	i = int(input())
	s = ""
	for k in range(1,i+1):
		s = s+str(k)
	list(permutationG(s,''))
	print('')
	j -= 1


def solve(lst, pos, num, n):
	if pos < n:
		for i in range(1, n+1):
			if i not in num[:pos]:
				num[pos] = i
				solve(lst, pos+1, num, n)
	else:
		lst.append("".join(map(str, num[:n])))
		
t=int(input())
for T in range(t):
	n = int(input())
	lst = []
	num = [0 for i in range(n)]
	solve(lst, 0, num, n)
	print((" ".join(lst)))


from itertools import permutations
for _ in range(eval(input())):
	s=""
	for i in range(eval(input())):
		s+=str(i+1)
	
	perms = [''.join(p) for p in permutations(s)]
	for i in perms:
		print(i, end=' ')
	print()



from itertools import permutations as p


t=int(input())
for i in range(t):
	n=int(input())
	s=''
	for i in range(1,n+1):
		s+=str(i)
	k=p(s)
	c=list(k)
	for a in c:
		print(''.join(a),end=' ')
	print()


t=eval(input())


def number(n):
	num=0
	for c in range(n):
		num=num*10+number_list[c]
	return num


for test in range(t):
	n=eval(input())
	print_list=[]
	number_list=[i for i in range(1,n+1)]

	def permute(k,n):
		if k==n-1:
			print_list.append(number(n))

		else:
			for j in range(k,n):
				temp=number_list[k]
				number_list[k]=number_list[j]
				number_list[j]=temp
				permute(k+1,n)
				temp=number_list[k]
				number_list[k]=number_list[j]
				number_list[j]=temp
				
	permute(0,n)
	print_list.sort()
	length=len(print_list)
	for p in range(length):
		print(print_list[p], end=' ')
	print()



def get_node(su,count,a,n):
	for i in range(1,n+1):
		if a[i]==0:
			su=(su*10)+i
			a[i]=1
			count=count+1
			if count==n:
				print(su, end=' ')
				su=int(su/10)
				a[i]=0
				count=count-1
				return
			else:
				get_node(su,count,a,n)
				a[i]=0
				su=int(su/10)
				count=count-1
		else:
			continue
T=int(input())
for t in range(T):
	su=0
	n=int(input())
	count=0
	a=[0 for x in range(n+1)]
	get_node(su,count,a,n)
	print()


from itertools import permutations
tcs = int(eval(input()))

def do(x):
	stringx = ''
	for x in range(1, intx+1):
		stringx += str(x)

	perms = [''.join(p) for p in permutations(stringx)]

	final = ''
	for p in perms:
		final += str(p)
		final += ' '

	return final.strip()

for tc in range(tcs):
	intx = int(eval(input()))
	print((do(intx)))


def findAll(a,i,N):
	if i == N-1:
		alle.append("".join(map(str,a)));
		return
	for j in range(i,N):
		temp = a[j]
		a[j] = a[i]
		a[i] = temp
		findAll(a,i+1,N)
		temp = a[j]
		a[j] = a[i]
		a[i] = temp
		
T = int(input())
alle = []
while T >0:
	alle = []
	N = int(input())
	a = [i+1 for i in range(0,N)]
	findAll(a,0,N)
	alle.sort()
	print(" ".join(alle))
	T-=1


		
		
		
		
		
		
		
		
		
		
		
		
		


def permutation(lst):
	if len(lst) == 0:
		return []

	if len(lst) == 1:
		return [lst]

	l = []

	for i in range(len(lst)):
	   m = lst[i]

	   remLst = lst[:i] + lst[i+1:]

	   for p in permutation(remLst):
		   l.append([m] + p)
	return l

		
		
for _ in range(eval(input())):
	k=eval(input())
	x=1
	s=str('')
	for item in range(k):
		s=s+str(x)
		x=x+1
	#print s
	n=list(str(s))
	#print n

	for p in permutation(n):
		print(''.join(p), end=' ')
	print('')
	  


import itertools
for _ in range(eval(input())):
	x=eval(input())
	s=[]
	for i in range(1,x+1):
		s.append(i)
	s1="".join(str(i) for i in s)
	#print s1
	for i in itertools.permutations(s1,len(s1)):
		print(''.join(i), end=' ')
	print() 
	


import sys

from itertools import permutations

L = ['1','2','3','4','5','6','7','8','9']

for case in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	l = list(permutations(L[:n],n))
	l.sort()
	s = ''
	for i in l:
		s +=  ''.join(i) + ' '
	print(s)



from itertools import permutations

for k in range(int(input())):
	st=''
	for i in permutations(list(range(1,int(eval(input()))+1))):
		for j in i:
			st+=str(j)
		st += ' '
	print(st[:-1])


def permutationG(input, s):
	if len(s) == len(input): yield s
	for i in input:
		if i in s: continue
		s=s+i
		for x in permutationG(input, s): yield x
		s=s[:-1]

j = int(input())
while (j > 0):
	i = int(input())
	s = ""
	for k in range(1,i+1):
		s = s+str(k)
	l = list(permutationG(s,''))
	for k in range(len(l)):
		print(int(l[k]), end=' ')
	print('')
	j -= 1


import itertools
for _ in range(eval(input())):
	for i in itertools.permutations(range(1,eval(input())+1)):
		print("".join(map(str,i)), end=' ')
	print()