K. K-Binary Repetitive Numbers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A number $$$N$$$ is called to be $$$K$$$-binary repetitive if it's binary representation using $$$K$$$ bits can be represented as a shorter binary string concatenated a number of times, for example, $$$N=10$$$ is $$$4$$$-binary repetitive since it's binary representation with $$$4$$$ bits ($$$1010$$$) can be represented as concatenating the binary string $$$10$$$ to itself, but, it is not $$$5$$$-binary repetitive since its binary representation using $$$5$$$ bits $$$01010$$$ can not be represented as a shorter binary string concatenated a number of times.

Given a number $$$K$$$, can you find how many different numbers $$$N$$$ are $$$K$$$-binary repetitive?

Input

The first line of input contains a single integer $$$T$$$ ($$$1 \leq T \leq 10^5$$$), the number of test cases. Each of the next $$$T$$$ lines contains a single integer number $$$K$$$ ($$$1 \leq K \leq 10^6$$$).

Output

For each test in the inpunt print a line containing one integer number, the number of different $$$N$$$ that are $$$K$$$-binary repetitive, since this number can be big print it modulo $$$10^9 + 7$$$.

Example
Input
2
1
2
Output
0
2