数兔子

题面描述

一对小兔子到第二个月长成大兔子，第三个月生下一对小兔子。每对小兔子到第三个月也生下一对小兔子。假设这些兔子都健康繁衍后代（兔子不会死亡），则第 n 个月一共有多少只兔子？

输入格式

第一行包含一个正整数 t ，代表测试用例组数。接下来是 t 行，每行一个整数n。

输出格式

共输出t行，每行一个正整数，为这个月所有兔子的数量。

样例输入1

3

10

11

20

样例输出1

55

89

6765

样例说明

数据范围

对于全部数据，保证有 1<= t <= 1000 ; $1<= n <= 90$