说明

欢迎来到 幸运 777 老虎机游戏！这款游戏以其复杂的数学挑战而闻名，只有最聪明的人才能赢得头奖。

这台老虎机由一个神秘的序列驱动——斐波那契数列。但这不是普通的斐波那契数列，它有一个受数字 $7$ 启发的变体，而 $7$ 是老虎机游戏中的幸运数字。

当你拉动 幸运 777 老虎机 的拉杆时，它会利用一个整数 $n$ 和 $7$ 的幂次生成一个巨大的数字：$7^{7^n}$。然而，这个数字如此庞大，以至于即使是最强大的计算机也无法直接处理它。

为了赢得头奖，你需要计算 $F_{7^{7^n}}$，即第 $7^{7^n}$ 个斐波那契数的最后 $10$ 位数字。

注意

斐波那契数列定义如下：

• $F_0 = 0$
• $F_1 = 1$
• $F_k = F_{k-1} + F_{k-2}$，对于 $k \ge 2$

输入格式

第一行包含一个整数 $t$，表示测试用例的数量。接下来的 $t$ 行，每行是一个测试用例，包含一个正整数 $n$。

输出格式

对于每个测试用例，输出一行，包含 $F_{7^{7^n}}$ 的最后 $10$ 位数字。

5
1
2
3
4
5

1353646637
3172443437
2364206637
9010523437
9481646637

提示

• $1 \le t \le 20$
• $1 \le n \le 10^9$

翻译由 DeepSeek V3.2 完成