考虑一个数组 $h$，其元素定义如下：

$$ \begin{aligned} h_0 &= 2, \\ h_1 &= 3, \\ h_2 &= 6, \\ h_n &= 4h_{n-1} + 17h_{n-2} - 12h_{n-3} - 16 \quad \text{对于 } n \ge 3. \end{aligned} $$

此外，定义两个数组 $b$ 和 $a$ 如下：

$$ \begin{aligned} b_n &= 3h_{n+1}h_n + 9h_{n+1}h_{n-1} + 9h_n^2 + 27h_nh_{n-1} - 18h_{n+1} - 126h_n - 81h_{n-1} + 192 \quad \text{对于 } n > 0, \\ a_n &= b_n + 4^n \quad \text{对于 } n > 0. \end{aligned} $$

你的任务是对于给定的整数 $n$，求出 $\lfloor \sqrt{a_n} \rfloor$ 的值。由于答案可能非常大，请将其对 $10^9 + 7$ 取模后输出。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量 ($1 \le T \le 1000$)。 每个测试用例包含一行，为一个整数 $n$ ($2 \le n \le 10^{15}$)。

输出格式

对于每个测试用例，输出一行，包含一个整数，即问题的答案。

样例

样例输入 1

3
4
7
9

样例输出 1

1255
324725
13185773