All Tracks Math Number Theory Primality Tests Problem

War Begins
Tag(s):

Easy-Medium

Problem
Editorial
Analytics

As you all know , We are at war and our brave soldiers are fighting for our country. KillCode is also one of the soldiers and is trying to help our country . To do this he needs a Launcher that is kept a small distance from him. Now , to get the Launcher , He needs to solve the following problem :

Problem consists of q queries one after the another and Killcode needs to tell the total numbers that can help to make a prime number .

For example : let say 7 is a prime number , following numbers that can help to make 7 are  :
 (1,6),(2,5)(3,4)

**Note **

Both numbers should be combination of even-odd. And (1,6),(6,1) both are counted as 1. So, ans for 7 is 3.

Now, for each query , Killcode would be given a number n and he has to tell the sum of all the numbers that can help to make specific prime number from 1 to n(both inclusive).

Constraints

1<=q<=10^5

1<=n<=5*10^6

Input

first line will contain an integer q , denoting the number of queries, next q lines will contain a number n.

Output

Output the answer in each single line.

Note Answer can be very large , use modulo 10^8+7.

As the time is very less, Help Killcode to solve this Problem So that he can save the country .
SAMPLE INPUT
3
2
8
11
SAMPLE OUTPUT
0
6
11
Explanation

For first testcase :

There is only 1 prime number less than equal to 2 that is 2 itself and 2 can't be made by combination of odd-even number .

For Second testcase :

There are 4 prime numbers less than equal to 8 ,

for 2 - 0 , for 3 - (1,2) , for 5 - (1,4),(2,3) , for 7 - (1,6),(2,5),(3,4)

So the total combinations are 6%(10^8+7) = 6

For Third testcase "

There are 5 prime numbers less than equal to 11 :

for 2 - 0 , for 3 - (1,2) , for 5 - (1,4),(2,3) , for 7 - (1,6),(2,5),(3,4) , for 11 - (1,10),(2,9),(3,8),(4,7),(5,6)

So the total numbers add upto 11%(10^8+7) = 11

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications