【题意】

有非负数列如下：

$f_1=1，f_2=2 ，f_3=6，f_n = ( 2 * f_{n-1}+ 2 * f_{n-2} - f_{n-3} )%P \ (4\le n)$

如果 $f_n$ 为负数，则 $f_n=(f_n \mod P + P) \mod P$ $(P=10^9+7)$

【输入格式】

第一行一个正整数$T \ (1 \le T \le 10^4 )$，表示询问次数。

下来 $T$ 个整数 $n \ (1 \le n \le 2^{62}-1 )$。

【输出格式】

输出一个数，即所有询问对应的$f_n$的异或和。

3
1
2
3

5

5
17
39
49
57
91

228142750