One, Two, Three Plus Four

Interview

Time limit1sMemory limit512 MB

Summary

Count the number of unordered sums of 1, 2, and 3 that add up to a given n, for each test case.

Level: Medium4 of 10
Topics: Dynamic programming, Combinatorics, Math, Implementation
Solved: No attempts yet

Problem

There are 4 ways to express the integer 4 as a sum of 1, 2, and 3. A sum must use at least one number. Two sums that differ only in the order of their terms count as the same way.

1+1+1+1
2+1+1 (1+1+2, 1+2+1)
2+2
1+3 (3+1)

Given an integer n, write a program that finds the number of ways to express n as a sum of 1, 2, and 3.

Input

The first line gives the number of test cases T. Each test case consists of one line and gives an integer n. n is a positive integer and is at most 10,000.

Output

For each test case, print the number of ways to express n as a sum of 1, 2, and 3.

Examples1

Example 1
Input
```
3
4
7
10
```
Expected output
```
4
8
14
```