설명

나무 선생님은 계단을 오르는데, 그는 매번 1급이나 2급을 걸을 수 있고, 계단의 급수를 입력하여 다른 주법 수를 구할 수 있다.예를 들어: 계단은 모두 3급이다. 그는 매번 한 계단을 걷거나 처음 한 계단을 걷거나 두 번째로 두 계단을 걷거나 처음 두 계단을 걷거나 두 번째로 한 계단을 걷거나 모두 세 가지 방법을 사용할 수 있다.

형식 입력

입력은 계단의 급수를 나타내는 양의 정수 $N$, $1≤N≤ 30$을 포함하는 여러 행을 포함합니다.

출력 형식

각 행에 해당하는 출력을 입력하는 다른 패스 수입니다.

샘플

5
8
10

8
34
89