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

这款老虎机由一个神秘的序列——斐波那契序列驱动。但它不是普通的斐波那契序列；它融入了受数字 7（老虎机游戏中的幸运象征）启发的元素。

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

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

输入格式

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

输出格式

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

数据范围

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

样例

输入样例 1

5
1
2
3
4
5

输出样例 1

1353646637
3172443437
2364206637
9010523437
9481646637

说明

斐波那契序列定义如下：

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