Integer 4 can be expressed as a sum of 1s, 2s, and 3s in seven di®erent ways as follows: 1 + 1 + 1 + 1; (1) 1 + 1 + 2; (2) 1 + 2 + 1; (3) 2 + 1 + 1; (4) 2 + 2; (5) 1 + 3; (6) 3 + 1: (7) 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.

Shanghai Jiaotong University Programming Contest 2004