Description

Teacher Tree is climbing stairs. He can choose to take either 1 step or 2 steps at a time. Given the total number of steps, calculate the number of distinct ways to climb the stairs.
For example: If there are 3 steps in total, he can:

• Take 1 step each time (1, 1, 1),
• Take 1 step first, then 2 steps (1, 2),
• Or take 2 steps first, then 1 step (2, 1).
  This results in a total of 3 distinct methods.

Input Format

The input consists of multiple lines, each containing a positive integer N, representing the number of steps (1 ≤ N ≤ 30).

Output Format

The number of distinct ways to climb the stairs. Each line of input corresponds to one line of output.

5
8
10

8
34
89