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