“And I am the Iron man”…
After, saying this line Tony Stark saves the world with his life. Before dying, he planted a tree called the Stark Tree. Weird, huh!!
The tree produces two types of leaf. One is Tony leaf and the other Thanos leaf. At the Nth day Stark Tree produces 2N leaves. Only one of which is Tony leaf and other leaves are Thanos leaf. If Nth day is a prime number then Tony leaf remove those Thanos leaf permanently. A number is said to be prime if it is only divisible by 1 and itself. The number 1 is not a prime by the way.
Now you have to find total number of remaining leaves at the end of the Nth day. As, the number could be very big you are requested to calculate the result modulo of 109 + 7.
Input
Input will start with the number of test cases T. The next T line contains an integer N.
Constraints
1 <= T <= 1000000
1 <= N <= 1000000
Output
For each T line you have to find the number of total leaves modulo 109 + 7.
Sample
| Input | Output |
|---|---|
2 3 4 | 4 20 |
Explanation
For the Sample,
When N = 1, 1 is not a Prime. So total leaves = 2
When N = 2, 2 is a Prime. All 3 Thanos leaves will be removed by Tony leaves. Only 1 leaf will remain. So, total leaves = 2 + 1 = 3
When N = 3, 3 is a Prime. So, total leaves = 3 + 1 = 4
When N = 4, 4 is not a Prime. So, total leaves 4 + 16 = 20.
