题目描述

$\mathtt{Pell数列}$ $a$ 的定义是这样的：$a_1 = 1, a_2 = 2, ... , a_n = 2 a_{n−1} + a_{n-2}(n>2)$。

给出一个正整数 $k$，要求 $\mathtt{Pell数列}$ 的第 $k$ 项模上 $32767$ 是多少。

输入格式

输入的第一行包含一个整数 $t$，代表测试数据的组数。

对于每一组测试数据，包含一行输入，每行输入包含一个正整数 $k$。

输出格式

对于每组测试数据，输出一行一个非负整数，代表 $\mathtt{Pell数列}$ 的第 $k$ 项模上 $32767$ 的值。

2
1
8

1
408

数据规模与约定

对于全部的测试点，保证 $1 \leq k \leq 10 ^ 6$。