1264: Adding 1s, 2s, and 3s

Integer 4 can be expressed as a sum of 1s, 2s, and 3s in seven different ways as follows: (1)1 + 1 + 1 + 1;
(2)1 + 1 + 2;
(3)1 + 2 + 1;
(4)2 + 1 + 1;
(5)2 + 2;
(6)1 + 3;
(7)3 + 1.
Write a program that determines the number of ways in which a given integer can be expressed as a sum of 1s, 2s, and 3s. You may assume that the integer is positive and less than 20.

The input consists of T test cases. The number of test cases (T ) is given in the first line of the input file. Each test case consists of an integer written in a single line.

Print exactly one line for each test case. The line should contain an integer representing the number of ways.

3
4
7
10

7
44
274