QQ向来对排列问题很感兴趣。什么全排列呀，置换群呀，都是QQ曾经研究过的问题。现在，一般难度的排列问题已经难不倒QQ了，QQ想要更高程度的挑战。于是QQ经常找全全和样样切磋很多高难度的题目。全全和样样都是研究排列的百年难得一遇的奇才，对此也是乐此不疲哦。

最近，他们发现他们三个人的昵称居然都是由重复的字组成的。这个可是一个很有趣的现象呀。于是，QQ的奇思妙想又出来了，他们每个人的昵称的字都提取出来，这样就获得了Q，全，样这三个字，他希望用这三个字重新组成新的昵称，每个字都可以用无限次，当然这样的昵称很可能很难听。 QQ又在这些排列上加了一个附加的条件，就是Q这个字母不能连续出现两次。

比如说，我们令Hn表示当昵称由n个字组成时，问有多少个符合条件的昵称。

例如：

H1=3，具体方案：Q，样，全

H2=8，具体方案：Q样，Q全，样Q，样全，样样，全Q，全样，全全

再令Sn=H1+H2+…+Hn-1+Hn;

QQ的问题出来了，他想知道Sn，但是这个Sn有可能太大了，所以QQ只想知道这个Sn对9937取余的结果。

先输入一个数T，表示有多少组测试数据

随后的T行，每行一个数n。

n的范围是1到1000000000；

对于每个数n，计算Sn mod 9937。