Pell数列
Description
Pell 数列 A1, A2, A3, ...的定义是这样的，$A_1 = 1, A_2 = 2, \dots, A_n = 2 * A_{n −1} + A_{n - 2} (n \gt 2) $。给出一个正整数 k，要求 Pell 数列的第 k 项模上 32767 是多少。
Format
Input
第 1 行是测试数据的组数 T，后面跟着 T 行输入。
每组测试数据占 1 行，包括一个正整数 k
(1 ≤ k < 1000000)。
Output
T行，每行输出对应一个输入。输出应是一个非负整数。
Samples
2
1
8
1
408
Limitation
1s, 1024KiB for each test case.