A45676.时空の穿越

在一个平行时空里，TS 出了名叫“亿大亿小”的题，题目简化过来是这样的：给定一个正整数 $N$，求一个数列 $F$ 中第 $N$ 项的值。但是，他在造数据时忘记写：

#define int __int18446744073709551616

导致这道题的输出数值特别小。最终这个问题在公开赛中被榜一大佬 SS 发现，TS 被网友骂了 $114514$ 年。现在这份题目文件不小心到了这个时空的 ST 电脑内，于是他就根据它出了这道题。

定义序列 $F$，它满足：

$$\begin{equation*} F_i= \begin{cases} 1, & 1\le (i\le 5)\\ F_{i-1}+2\times F_{i-2}+3\times F_{i-3}+5\times F_{i-4}+8\times F_{i-5}, & (i \ge 6)\\ \end{cases} \end{equation*}$$

给定一个正整数 $N$，定义 $Ans$ 如下：

$$\begin{equation*} Ans= \begin{cases} F_N\mod 2^{32}, & F_N\mod 2^{32}\lt 2^{31}\\ (F_N\mod 2^{32})-2^{32}, & F_N\mod 2^{32}\ge 2^{31}\\ \end{cases} \end{equation*}$$

请你求出 $Ans$ 的值。

输入共 $T+1$ 行：

第一行 $1$ 个正整数 $T$，表示测试数据数量；

对于每个测试数据，有 $1$ 个正整数 $N$，占一行。

对于每个测试数据，输出 $1$ 个正整数，表示该测试数据对应的 $Ans$ 的值，以换行符隔开。

【数据范围】

对于所有的数据，保证：

$1\le T\le 10^3,1\le N\leq 2^{64}-1$

测试点	$N\le$
1,2,3	$10^3$
4~10	$2^{64}-1$

本题测试点等分。

【样例解释】

样例组 #1：三组测试的解释如下：

$\because1\le 5\\\therefore F_1=1$

$\because6\ge 6\\\therefore F_6=F_5+2\times F_4+3\times F_3+5\times F_2+8\times F_1=19$

$\because F_{26}=3406986289\\\ \ \ \ F_{26}\mod 2^{32}=3406986289\ge 2^{31}\\\therefore Ans=3406986289-2^{32}=-887981007$

【特殊说明】

• 让 int 直接溢出在原则上是不被允许的，因为这是未定义行为，即在不同编译器中产生的结果可能不同，有些编译器甚至返回 RE。所以对于这道题，你应该使用 long long 对 $2^{32}$ 取模或者使用 unsigned int 自然溢出来计算。