Pell数列

题目描述

a₁,a₂,a₃, ...的定义是这样的，a₁ = 1, a₂ = 2, ... , a_n = 2 * a_n-1 + a_n-2  (n>2)。

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

输入

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

输出

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

输入样例

2
1
8

输出样例

1
408

分解因数

给出一个正整数 a， 要求分解成若干个正整数的乘积， 即 a = a₁ * a₂ * a₃ * ... * a_n， 并且 1 < a₁ ≤ a₂ ≤ a₃ ≤ ... ≤ a_n， 问这样的分解的种数有多少。 注意到 a = a 也是一种分解。

输入

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

输出

n 行， 每行输出对应一个输入。 输出应是一个正整数， 指明满足要求的分解的种数

样例输入

2
2
20

样例输出

1
4