题目描述

Pell数列$a_1, a_2, a_3,...$的定义如下： $a_1 = 1, a_2 = 2, an = 2 \times a{n-1} + a_{n-2} \quad (n > 2)$ 给出正整数k，求Pell数列第k项模32767的结果。

时间限制：3000ms 内存限制：65536KB

输入格式

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包含一个正整数k（$1 \leq k < 1000000$）。

输出格式

n行，每行输出对应输入的结果，为非负整数。

样例输入

2
1
8

样例输出

1
408