The Fibonacci sequence is named after Italian mathematician Leonardo of Pisa, later known as Fibonacci. The sequence starts with 0 and 1. Each of the next numbers in the sequence is the sum of the two preceding ones. The beginning of the sequence is thus:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Input

An integer \(n \in \mathbb{N}\).

Output

The numbers in the Fibonacci sequence, each on a separate line. Print the numbers until the first number that exceeds \(n\).

Example

Input:

10

Output:

0
1
1
2
3
5
8
13