#T1189. Pell数列

Pell数列

题目描述

Pell 数列 a1,a2,a3,a_1,a_2,a_3, \dots 的定义是这样的:

  • a1=1a_1 = 1
  • a2=2a_2 = 2
  • \dots
  • an=2an1+an2(n>2)a_n = 2 a_{n−1} + a_{n-2}(n>2)

给出一个正整数 kk,求 Pell 数列的第 kk 项模上 3276732767 是多少。

输入

11 行是测试数据的组数 nn,后面跟着 nn 行输入。

每组测试数据占 11行,包括一个正整数 kk1k<1061\le k\lt 10^6)。

输出

nn 行,每行输出对应一个输入。输出应是一个非负整数。

2
1
8
1
408