$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 \leq k < 1000000)$。

$n$ 行，每行输出对应一个输入。输出应是一个非负整数。