Drop links or images here to add them to the editor.

Fibonacci with While ⭐⭐⭐

What is the Fibonacci sequence?

The Fibonacci sequence is a series of numbers where each number is the sum of the two before it. It starts with 1 and 1:

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

For example: 2 = 1 + 1, 3 = 1 + 2, 5 = 2 + 3, and so on.

Task

Read an integer N and print the first N numbers of the Fibonacci sequence, one per line.

Input

One integer:

  1. N

Output

Print the first N Fibonacci numbers, one per line.

Example

Input:

7

Output:

1
1
2
3
5
8
13