题目背景

$\verb|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$ 项 %123456 的结果是多少。

输入格式

第 $1$ 行是测试数据的组数 $n$ ，后面跟着 $n$ 行输入。每组测试数据占 $1$ 行，仅包括一个正整数 $k$。

输出格式

共有 $n$ 行，第 $i$ 行是一个整数，对应输入的第 $i$ 组测试数据的计算结果。

输入输出样例

2
1
8

1
408

说明/提示

👀️ 对于$100\%$ 的数据，$1 \leq n \leq 100000,1 \leq k \leq 1000000$。