Description

There is a staircase with n steps (71 > n > 0). When climbing the stairs, you can take 1 step at a time, 2 steps at a time, or 3 steps at a time. Write a program to calculate the total number of distinct 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 is 0, indicating the end of the test cases.

Output Format

Each line of output corresponds to the result of the input line, which is the number of distinct ways to climb the stairs.

1
2
3
4
0

1
2
4
7