Adding 1, 2, and 3

Interview

Time limit1sMemory limit512 MB

Summary

Count the ordered ways to write n as a sum of 1, 2, and 3 for each test case with n below 11.

Level: Easy3 of 10
Topics: Dynamic programming
Solved: No attempts yet

Problem

There are 7 ways to write the integer 4 as a sum of 1, 2, and 3. A sum must use at least one number, and two sums that use the same numbers in a different order count as different ways.

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1

Given an integer $n$ , write a program that finds how many ways there are to write $n$ as a sum of 1, 2, and 3.

Input

The first line contains the number of test cases $T$ . Each test case is one line holding an integer $n$ . $n$ is positive and smaller than 11.

Output

For each test case, print the number of ways to write $n$ as a sum of 1, 2, and 3, one per line.

Examples1

Example 1
Input
```
3
4
7
10
```
Expected output
```
7
44
274
```