题目描述
植物园观察到一个竹节生长数列 $a_1, a_2, a_3, \ldots$： $a_1 = 1$，$a_2 = 2$，此后每节满足 $a_n = 2a_{n-1} + a_{n-2}$（$n > 2$）。
给出若干个询问，每个询问求第 $k$ 项对 $32767$ 取余的值。
输入格式
第一行一个整数 $t$，为询问组数； 接下来 $t$ 行，每行一个正整数 $k$（$1 \le k < 10^6$）。
输出格式
$t$ 行，每行一个非负整数：第 $k$ 项对 $32767$ 取余的值。
数据范围
$$1 \le t,\quad 1 \le k < 10^6$$