Mr. X wants to buy a necklace for his girlfriend.
The available necklaces are bi-colored (red and blue beads).

Mr. X desperately wants to impress his girlfriend and knows that she will like the necklace only if every prime length continuous sub-sequence of beads in the necklace has more or equal number of red beads than blue beads.

Given the number of beads in the necklace N, Mr. X wants to know the number of all possible such necklaces.

Note: - It is given that the necklace is a single string and not a loop.

Input Format

The first line of the input contains an integer T, the number of testcases.

T lines follow, each line containing N, the number of beads in the necklace.

Constraints

1 ≤ T ≤ 10^{4}

2 ≤ N ≤ 10^{18}

Output Format

For each testcase, print in a newline, the number of such necklaces that are possible. If the answer is greater than or equal to 10^{9}+7, print the answer modulo ( % ) 10^{9}+7.

Sample Input

2
2
3

Sample Output

3
4

Explanation

For the first testcase, valid arrangement of beads are

BR RB RR

For the second testcase, valid arrangement of beads are

BRR RBR RRR RRB

见题面

见题面