P1155 - Pell数列
题目描述
Pell数列$a_1, a_2, a_3$, ...的定义是这样的，$a_1 = 1$, $a_2 = 2$, ... , $a_{n} = 2 \times a_{n - 1} + a_{n - 2}$ (n > 2)。
给出一个正整数k，要求Pell数列的第k项模上32767是多少。
输入格式
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数k (1 ≤ k < 1000000)。
输出格式
n行，每行输出对应一个输入。输出应是一个非负整数。
样例 #1
样例输入 #1
2
1
8
样例输出 #1
1
408
测试点数目
共10个测试点，每个测试点10分
时间与内存限制
每个测试点时间：1000ms（1.0s），内存：256MiB
输入输出模式
本OJ支持两种输入输出模式
1. 标准输入输出模式：
直接从标准输入和标准输出读写数据，不需要使用freopen进行文件输入输出重定向
2. 文件输入输出模式（国内信奥赛输入输出模式）:
从文件中读写数据，需要使用freopen进行输入输出重定向
本题输入文件名为：P1155.in，输出文件名为：P1155.out