No submission language available for this problem.

Background

Special for beginners, ^_^

Description

新斐波那契的当前项等于前三项之和（注：第一项为 1，第二项为 2，第三项为 3 ）,现在问新斐波那契的第 n 项的值为多少。

注意请用递归完成

例根据新斐波那契当前项为前三项之和,第四项为前一二三项的和也就是 1+2+3=6

Format

Input

第一行一个整数 T 表示将有 T 组测试询问，每组测试数据占一行，每行一个整数 n，表示该组询问第 n 个新斐波那契数列数是多少。

Output

输出有 T 行，每行一个整数表示相应测试组的答案

Samples

4
1
4
15
20

1
6
4841
101902

Limitation

数据范围：

50% 数据 0<n≤20

100% 数据 0<n≤50

1s, 1024KiB for each test case.