Staircase Climbing Problem

Given a staircase with n steps, you are allowed to take either 1, 2, or 3 steps at a time. Your task is to determine the number of distinct ways to reach the top of the staircase.

The problem can be formulated using the recurrence relation: \[ f(n) = f(n-1) + f(n-2) + f(n-3), \] with the base cases: \[ f(0)=1,\quad f(1)=1,\quad f(2)=2. \]

For example, when n=4, there are 7 distinct ways to climb the staircase.

inputFormat

The input is given via stdin and consists of:

1. An integer T representing the number of test cases.
2. For each test case, a single integer n representing the number of steps in the staircase.

outputFormat

For each test case, output the number of distinct ways to reach the top of the staircase on a new line via stdout.

## sample

3
2
3
4

2
4
7

</p>