时间限制：1秒　　内存限制：256M

---

【题目描述】

　　Pell数列 \(a_1, a_2, a_3, ...\) 的定义是这样的，\(a_1 = 1, a_2 = 2, ... , a_n = 2 × a_{n − 1} + a_{n - 2} (n > 2)\)。
　　给出一个正整数 \(k\)，要求Pell数列的第k项模上 32767 是多少。

【输入格式】

　　第1行是测试数据的组数 \(n\)，后面跟着 \(n\) 行输入。每组测试数据占 1 行，包括一个正整数 \(k\)。

【输出格式】

　　输出 \(n\) 行，每行输出对应一个输入。输出应是一个非负整数。

【输入输出样例】

　Input

2
1
8

　Output

1
408

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤k≤10000000\)。

【来源】

　　Mr.he