FIBEASY - Fibonacci Easy

no tags 

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 


Added by:Simon
Date:2013-04-27
Time limit:0.203s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET