SOLVE

LATER

War Begins

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

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++,
C++14,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Julia,
Kotlin,
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Swift,
Visual Basic

Initializing Code Editor...

{"b8fc24d": "/pagelets/recommended-problems/algorithm/war-begin/", "b8fc240": "/pagelets/problems-hint/algorithm/war-begin/", "b8fc210": "/pagelets/suggested-problems/algorithm/war-begin/", "b8fc231": "/pagelets/problem-author-tester/algorithm/war-begin/", "b8fc1f4": "/pagelets/show-submission/algorithm/war-begin/"}

realtime.hackerearth.com

80

cf49e923dc6de418518135f577c29cd18bc95597

58a29e5cae2309f04b28

/realtime/pusher/auth/