1391:数列-2

有一个数列，a[1] = 1，a[2] = 2，当 n >= 3 时：a[n] = 4 * a[n - 1] - 3 * a[n - 2]，你的任务是计算这个数列的第 x 项。

第一行是一个正整数 T 代表测试案例的数量。(1 <= T <= 1000)

每组案例包含一个正整数 x 。

对于30%的样例，x <= 1e3。

对于60%的样例，x <= 1e6。

对于100%的样例，x <= 1e10。

针对每组案例，输出数列的第 x 项，然后换行。

由于答案可能很大，所以你只需要输出它对（2 ^ 31）取模之后的结果。

3

1

2

10

1

2

9842