题目描述

P1=1，P2=2，Pn=2P(n-1)+P(n-2)，输出指定项模32767。

输入格式

第一行测试组数，随后各行 k。

输出格式

每组一行。

样例

2
1
8

1
408

数据范围

1≤k<1000000。