暂无测试数据。

题目描述

Pell 数列 \(a_1,a_2,a_3 \cdots \) 的定义是这样的：

\(a_1=1\),\(a_2=2\),\(\cdots\),\(a_n=2*a_{n-1}+a_{n-2}  (\)n>2$)。

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

输入

第 1 行，是测试数据的组数\(n\)，
后面跟着 \(n\) 行输入。
每组测试数据占 1 行，
包括一个正整数 \(k\) 。

输出

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

样例输入

2
1
8

样例输出

1
408

数据范围限制

\(1 \leq n \leq 10\),\(1 \leq k < 10^6\)

来源

基础篇练习1.2