jerry99的数学能力很强，经常会研究一些复杂的数学问题。

已知数列 $a_1, a_2, ..., a_n$，其中 $a_i$ 是最接近 $\sqrt i$ 的整数。

jerry99想知道 $a_1 \times a_2 \times ... \times a_n$ 的结果，但是他的作业太多了，你能帮帮他吗？

由于结果可能很大，请将结果对 $10^9+7$ 取模。

第一行为一个整数 $T\ (1 \le T \le 100)$ ，表示一共有 $T$ 组数据。
对于每组数据：
输入一行，包含一个整数 $n\ (1\le n\le 10^9)$。

对于每组数据，输出一行一个整数，表示 $\Pi_{i = 1}^{n} a_i \pmod {10^9+7}$。

对于前 $5$ 组数据：
$a_1=1$
$a_2=1$
$a_3=2$
$a_4=2$
$a_5=2$
故可求得相应结果。