Count Ways to Climb Staircase

You are given a staircase with ( n ) steps. Your task is to calculate the number of distinct ways to reach the top when you can take either 1, 2, or 3 steps at a time. The recurrence relation for the number of ways is given by [ \text{ways}(n) = \text{ways}(n-1) + \text{ways}(n-2) + \text{ways}(n-3), ] with the base cases defined as:

• ( \text{ways}(1) = 1 )
• ( \text{ways}(2) = 2 )
• ( \text{ways}(3) = 4 )

The input consists of multiple test cases. For each test case, an integer ( n ) is provided, which denotes the number of steps in the staircase. The input is terminated by a line containing a single zero (0), which should not be processed. For each test case, output the number of distinct ways to climb the staircase.

inputFormat

The input is given via standard input (stdin) and consists of several lines. Each line contains a single integer ( n ) (( 1 \leq n \leq 10^3 ), for example) representing the number of steps in the staircase. The input terminates with a line containing the integer 0, which should not be processed.

outputFormat

For each test case (each integer ( n ) given in the input before the terminating 0), output the number of distinct ways to climb the staircase on a new line to standard output (stdout).## sample

5
4
7
0

13
7
44