Problem Description

You know the date type double can guarantee the precision about 15 or 16 digits.
But in this problem, you have to calculate ⌊(2+3)2n⌋ mod 1024\left\lfloor\left(\sqrt{2}+\sqrt{3}\right)^{2n}\right\rfloor\bmod 1024.
For example, when n=2n=2, (2+3)4=97.9897⋯\left(\sqrt{2}+\sqrt{3}\right)^4=97.9897\cdots, ⌊(2+3)4⌋ mod 1024=97\left\lfloor\left(\sqrt{2}+\sqrt{3}\right)^{4}\right\rfloor\bmod 1024=97.

Input

The first line of input gives the number of cases, TT. TT test cases follow, each on a separate line. Each test case contains one positive integer nn. (1≤n≤1091 \le n \le 10^9)

Output

For each input case, you should output the answer in one line.

Sample Input

1
2
3
4
3
1
2
5

Sample Output

1
2
3
9
97
841

Idea

(2+3)2n=(5+26)n=∑k=0nCnk⋅5k⋅(26)n−k\left(\sqrt{2}+\sqrt{3}\right)^{2n}=(5+2\sqrt 6)^n=\sum\limits_{k=0}^nC_n^k\cdot5^k\cdot (2\sqrt 6)^{n-k}，将有理项和无理项分开；不妨设 (5+26)n=xn+yn6(5+2\sqrt 6)^n=x_n+y_n\sqrt 6，其中 xn,yn∈N∗x_n,y_n\in\mathbb N^\ast；根据二项式的性质，又有 (5−26)n=xn−yn6(5-2\sqrt6)^n=x_n-y_n\sqrt 6。
首先，(5+26)n+(5−26)n=2xn(5+2\sqrt 6)^n+(5-2\sqrt6)^n=2x_n，故 ⌊(5+26)n⌋=⌊2xn−(5−26)n⌋=2xn−1\lfloor(5+2\sqrt 6)^n\rfloor=\lfloor2x_n-(5-2\sqrt6)^n\rfloor=2x_n-1。
显然有递推式

$$ \begin{aligned}&(5+2\sqrt 6)^n\\=&(5+2\sqrt 6)^{n-1}\cdot (5+2\sqrt 6)\\=&(x_{n-1}+y_{n-1}\sqrt 6)\cdot(5+2\sqrt 6)\\=&5x_{n-1}+2\sqrt 6x_{n-1}+5\sqrt 6y_{n-1}+12y_{n-1}\\=&(5x_{n-1}+12y_{n-1})+(2x_{n-1}+5y_{n-1})\sqrt 6\end{aligned} $$

又有定义 (5+26)n=xn+yn6(5+2\sqrt 6)^n=x_n+y_n\sqrt 6，故得到

xn=5xn−1+12yn−1yn=2xn−1+5yn−1x_n=5x_{n-1}+12y_{n-1}\\ y_n=2x_{n-1}+5y_{n-1}

可构造矩阵递推式

$$ \begin{pmatrix}5&12\\2&5\end{pmatrix}\begin{pmatrix}x_{n-1}\\y_{n-1}\end{pmatrix}=\begin{pmatrix}x_n\\y_n\end{pmatrix} $$

即

$$ \begin{pmatrix}5&12\\2&5\end{pmatrix}^{n-1}\begin{pmatrix}x_1\\y_1\end{pmatrix}=\begin{pmatrix}x_n\\y_n\end{pmatrix} $$

全程在  mod 1024\bmod 1024 的意义下计算，不存在浮点误差和数值溢出的问题；答案为 (2xn−1) mod 1024(2x_n-1)\bmod 1024，时间复杂度为 O(log⁡n)O(\log n)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int MOD=1024;
struct Matrix{
	ll m[3][3];
	Matrix(){
		memset(m,0,sizeof(m));
	}
};
Matrix operator*(const Matrix& x,const Matrix& y){
	Matrix res;
	for(int i=1;i<=2;i++){
		for(int j=1;j<=2;j++){
			for(int k=1;k<=2;k++){
				res.m[i][j]+=x.m[i][k]*y.m[k][j];
				res.m[i][j]%=MOD;
			}
		}
	}
	return res;
}
Matrix quickMatrixPow(Matrix a,ll b){
	Matrix res;
	res.m[1][1]=res.m[2][2]=1;
	while(b){
		if(b&1){
			res=res*a;
		}
		a=a*a;
		b>>=1;
	}
	return res;
}
int main(){
	ios::sync_with_stdio(false);
	int _;
	for(cin>>_;_;_--){
		int n;
		cin>>n;
		Matrix A;
		A.m[1][1]=A.m[2][2]=5;
		A.m[1][2]=12;
		A.m[2][1]=2;
		A=quickMatrixPow(A,n-1);
		ll a=1ll*(5*A.m[1][1]+2*A.m[1][2])%MOD;
		cout<<(2*a-1+MOD)%MOD<<endl;
	}
	return 0;
}