This is Fibonacci madness.
Given a number n. Print the first n Fibonacci numbers in reverse order.

Input:

First line is number T denoting number of test cases.
T lines follow. Each line has number N.

Output:

Print the first n Fibonacci numbers in reverse order for all test cases.

Constraints:

1 ≤ T ≤ 10

0 ≤ N ≤ 100

Example

Input:
3

1

7

4
Output:
0

8 5 3 2 1 1 0 

2 1 1 0

SAMPLE INPUT
3
1
7
4

SAMPLE OUTPUT
0 
8 5 3 2 1 1 0 
2 1 1 0
new = [0, 1]
while len(new) != 100:
	new.append((new[len(new) - 1] + new[len(new) - 2]))
new.sort(reverse=True)

for _ in xrange(input()):
	x=int(input())
	to=100-x
	to_print = ""
	for i in xrange(to,100):
		to_print+=str(new[i])+" "
	print to_print