Problem: 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

Solution (in PYTHON):

Solution:
for t in range(input()):
 lst=[]
 lst.append(0)
 lst.append(1)
 lst.append(1)
 n=int(raw_input())
 if n==1:
  print 0
  continue
 elif n==2 or n==3:
  print "1 1 0"
  continue
 i=3
 while i<n:
  lst.append(lst[i-1]+lst[i-2])
  i=i+1
 i=n-1
 while i>=0:
  print lst[i],
  i=i-1
 print