【递归】Pell数列

题目描述

Pell数列 $a_1，a_2，a_3……$ 的定义是这样的，$a_1 = 1，a_2 = 2，a_n = 2a_{n-1} + a_{n-2}(n > 2)$。

给出一个正整数 k，求 Pell 数列的第 k 项的值是多少。

注意：请用递归完成

输入格式

第 1 行是测试数据的组数 $n (0 < n \le 100)$。

接着输入 n 行，每一行输入一个正整数 $k (0 < k \le 30)$，表示要求 Pell 数组第 $k$ 项的值。

输出格式

输出有 n 行，每一行输出对应的 Pell 数列的项。

输入输出样例 #1

输入 #1

3
1
2
5

输出 #1

1
2
29

说明/提示

样例说明：

样例总共有 3 组测试数据。

第 1 组求 Pell 数组的第 1 项，即输出 1；

第 2 组求 Pell 数组的第 2 项，即输出 2；

第 3 组求 Pell 数组的第 5 项，即输出 29。