#1538 Fibonacci - 3

123  1 s   128 MB  

Description


G[i] = G[i-1] + G[i-2] + G[i-3]  : if i > 3,
G[i] = 1                                   :  otherwise.

로 정의되는 피보나치 수열을 Fibonacci-3라 하자.
n(1<=n<=60)이 주어질때 이에 해당되는 n번째 Fibonacci-3수열을 출력하라.

Input

테스트 케이스 수 T와 T개의 n(1<=n<=60)이 주어진다.

Output

각값에 해당되는 Fibonacci-3값을 출력.

Sample Input

Sample Output

5
1
2
3
4
5
1
1
1
3
5