A4823 | 时空の穿越

在一个平行时空里，TS 出了名叫“亿大亿小”的题，题目简化过来是这样的：给定一个正整数 $N$，求一个数列 $F$ 中第 $N$ 项的值。但是，他在造数据时忘记写：
```cpp
#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$ 的值，以换行符隔开。