Source : 信息学奥赛一本通训练指导教程
Description

PellPell 数列a1,a2,a3a_1,a_2,a_3…是这样定义的:a1=1,a2=2,an=2×an1+an2(n>2)a_1=1,a_2=2,a_n=2\times a_{n-1}+ a_{n-2}(n>2),给出一个正整数kk,要求Pell数列的第kk项模上3276732767是多少。

Input

第1行是测试数据的组数nn,后面跟着nn行输入。每组测试数据占11行,包括一个正整数k(1k<1000000)k(1 \leq k < 1000000)

Output

nn 行,每行输出对应一个输入。输出应是一个非负整数。

Sample Input
2
1
8
Sample Output
1
408