The above sequence is called the Fibonacci sequence and is defined as follows:

• ~F_1 = F_2 = 1 ~
• ~F_n = F_{n-1} + F_{n-2} ~

Write a program to compute the first ~ n ~ Fibonacci numbers.

Input

• A single line containing a positive integer ~ n ~ (~ 1 \leq n \leq 10^3 ~).

Output

• Print the first ~n~ Fibonacci numbers on ~n~ lines.

Sample Input

10 

Sample Output

1 
1 
2 
3 
5 
8 
13 
21 
34 
55