Description

Integer 4 can be expressed as a sum of 1s, 2s, and 3s in seven different 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 36.


Input

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.

Output

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

Sample Input


3
4
7
10


Sample Output


7
44
274


Source

#include <stdio.h>

int main()
{
    static int f[37]={1};
    for(int i=1;i<37;i++){
        f[i]=f[i-1]+f[i-2]+f[i-3];
    }    
    int n;
    while(scanf("%d",&n)!=EOF){
        printf("%d\n",f[n]);
    }    
}

lz你的代码在数据结构里面有,是老静提供得算法结合里面的.....你找找啊