题目描述

Pell 数列 $a_1, a_2, a_3, \dots$ 的定义如下：
$a_1 = 1$，$a_2 = 2$，
对于 $n > 2$，有 $a_n = 2 \times a_{n-1} + a_{n-2}$。

现在给定一个正整数 $k$，要求输出 Pell 数列的第 $k$ 项对 $32767$ 取模的结果。

输入格式

第一行是一个整数 $n$，表示测试数据的组数。
接下来 $n$ 行，每行一个正整数 $k$，表示要求第 $k$ 项。

输出格式

输出共 $n$ 行，每行一个整数，表示对应输入的 Pell 数列第 $k$ 项模 $32767$ 的结果。

样例

2
1
8

1
408

数据范围

• $1 \le n < 10$
• $1 \le k < 10^6$
• 模数为 $32767$