描述：

小丁在听网课时听到了一种数列，小丁把他取名为“BUG数列”。

数列 $a_1,a_2,a_3...$ 的定义是这样的，$a_1 = 1, a_2 = 2, ... , a_n = 2*a_{n-1} + a_{n-2}$ $(n>2)$。给出一个正整数 $k$，他想知道数列的第 $k$ 项是多少。

输入：

第 $1$ 行是测试数据的组数 $n$。

第 $2$ 到 $n+1$ 行是 $n$ 行输入。每组测试数据占 $1$ 行，包括一个正整数 $k$。

输出：

$n$ 行，每行输出对应一个输入。

样例 #1

样例输入 #1

2
1
8

样例输出 #1

1
408

提示

对于 $100\%$ 的数据，$1 \le k \le 10^6$，$1 \le n \le 10^2$。