题目描述
Pell 数列 $a_1, a_2, a_3, \dots$ 的定义是这样的：
- $a_1 = 1$
- $a_2 = 2$
- $a_n = 2\times a_{n-1} + a_{n-2}$ $(n \ge 2)$
给出一个正整数 $k$，求 Pell 数列的第 $k$ 项 $a_k$ 对 $32767$ 取模后的结果是多少。
输入格式
第一行包含一个整数 $T$，表示测试数据组数。
每组数据占一行，包含一个正整数 $k$.
- $1 \le T \le 10\,000$
- $1 \le k \le 1\,000\,000$
输出格式
$T$ 行，每行输出对应一个输入。输出应是一个非负整数，表示 $a_k \bmod 32767$.