问题1070--Pell数列

1070: Pell数列

时间限制: 1 Sec  内存限制: 256 MB
提交: 96  解决: 36
[状态] [提交] [命题人:]

题目描述

Pell数列是这样定义的:a1=1,a2=2,...,an=2an-1+an-2
现在求出Pell数列的第k项模上32767的余数是多少。

输入

第一行为正整数T,表示存在T组测试数据。
每组测试数据输入一行包含一个正整数k(1<=k<=1000000)。

输出

对于每组测试数据输出一行表示答案。

样例输入 Copy

2
1
8

样例输出 Copy

1
408

来源/分类

 入门题