4000074 - Pell数列
Time Limit : 1 秒
Memory Limit : 128 MB
Pell 数列 a_1，a_2，a_3 \cdots 的定义是这样的：a_1=1,a_2=2, ... , a_n=2 \times a_{n-1}+a_{n-2} (n>2)。给出一个正整数 k，要求 Pell 数列的第 k 项是多少。
Input
第 1 行是测试数据的组数 n，后面跟着 n 行输入。每组测试数据占 1 行，包括一个正整数 k ( 1 \le k<1000000 )。
Output
n 行，每行输出对应一个输入。输出应是一个非负整数。
数据范围 1 \le n \le 20,1 \le k \le 20。
Examples
Input
2 1 8
Output
1 408
Hint
开一个数组模拟即可，当然如果不会数组，滚动几个变量也是可以的。