Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Stark Tree

By ssavi1994 · Limits 2s, 512 MB

“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

InputOutput
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.

    Discussion

    Statistics


    87% Solution Ratio

    YouKnowWhoEarliest, 6M ago

    prodip_bsmrstuFastest, 0.1s

    prodip_bsmrstuLightest, 14 MB

    AlfehsaniShortest, 657B

    Submit

    Login to submit