Description

A staircase has $n$ steps ($0 < n < 71$). When climbing the stairs, you can take either 1, 2, or 3 steps at a time. Write a program to calculate the number of different ways to climb the stairs.

Input Format

Each line of input contains a test case, which is the number of steps $n$. The last line contains 0, indicating the end of the test cases.

Output Format

For each line of input, output one line containing the number of different ways to climb the stairs.

Sample

1
2
3
4
0

1
2
4
7