In mathematics, the Fibonacci numbers (F_n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the previous two numbers.

The first number in the sequence (F₁) is 0, the second number (F₂) is 1.

F₁ = 0
F₂ = 1
F₃ = F₁ + F₂ = 0 + 1 => 1
F₄ = F₂ + F₃ = 1 + 1 => 2
F₅ = F₃ + F₄ = 1 + 2 => 3
F₆ = F₄ + F₅ = 2 + 3 => 5
.
.
.
F_n = F_n-2 + F_n-1

Given a number (n), print the first n fibonacci numbers.

Example:

The first 6 fibonacci numbers are 0 1 1 2 3 5.

Input Format

The first line contains T denoting the no. of test cases.
Next T lines each containing a number.

Output Format

The first n fibonacci numbers.

Examples

Sample Input

2
1
8

Expected Output

0
0 1 1 2 3 5 8 13

Explanation

F₁ = 0
0, 1, 0+1, 1+1, 1+2, 2+3, 3+5, 5+8

Constraints:

n <= 40