There's an array that is generated by following rule.
$h_0=2,h_1=3,h_2=6,h_n=4h_{n-1}+17h_{n-2}-12h_{n-3}-16$
And let us define two arrays ${b_n} and {a_n}$ as below.
$b_n=3h_{n+1} h_n+9h_{n+1} h_{n-1}+9h_n^2+27h_n h_{n-1}-18h_{n+1}-126h_n-81h_{n-1}+192(n>0)$
$a_n=b_n+4^n$
Now, you have to print $\left \lfloor √(a_n ) \right \rfloor $ , n>1.
Your answer could be very large so print the answer modular 1000000007.

The first line of input contains T (1 <= T <= 1000) , the number of test cases.
Each test case contains one integer n (1 < n <= $10^{15}$) in one line.

For each test case print ⌊��(a_n )⌋ modular 1000000007.