今天神犇的弟弟神神犇的幼儿园新进了两箱积木，每箱100个，分别是红色和蓝色。于是神神犇和他的小伙伴们开始玩这些积木：所有n块积木排成一排且蓝色必须两个“一组”，“一组”的必须相邻且不能属于多个组。当他们玩了若干次之后，神犇犇突然想知道一共用了n个积木的情况下，有多少种摆法。

第一行，一个整数t，表示测试数据组数。

接下来t行，每行一个整数n表示一共用了多少块积木。

对于100%的数据：

1\le t \le 50 。

1\le n \le 36 。

按输入顺序每行一个整数，表示对应方案数。

扩展思考：

1、本题的多组询问，是否可以通过一次计算得到结果而后直接输出？

2、若数据中n>200则答案与n为多少相同？

3、若n=37你的程序会输出39088169吗？