Explanation

Teacher Tree climbs stairs. He can take 1 or 2 steps at a time, input the number of steps, and find different ways to take them. For example, the staircase has a total of 3 levels, and he can walk one level each time, or walk one level the first time and two levels the second time, or walk two levels the first time and one level the second time. There are a total of 3 methods.

Input format

The input contains several rows, each row containing a positive integer N representing the number of stair steps, with $1≤N≤30$.

Output format

Different stroke numbers, each line of input corresponds to one line of output.

Example

5
8
10

8
34
89