Print the n first Fibonacci numbers. You must know that the first 2 Fibonacci numbers are 1, 1.

Input

The first line will contain a number C (1 <= C <= 100). Then, will follow C lines, each one with a number N (1 <= M <= 45).

Output

For each N you must print the N first Fibonacci, each one followed by a space.

Example

Input:
5
1
2
3
5
8

Output:
1 
1 1 
1 1 2 
1 1 2 3 5 
1 1 2 3 5 8 13 21