The country of Horangabad is in a state of war. The soldiers are fighting for their country. Army Officer Ranjeet is also one of the soldiers and is trying to help his country, Horangabad . To do this he needs a catapult that is kept at a small distance from him. Since the time is less, so you are hired to help him in solving this puzzle:
Puzzle consists of z queries one after the another and Officer Ranjeet needs to tell the total numbers that can help make him a prime number.
Now, for each query , Officer Ranjeet would be given a number t and he has to tell the sum of all the numbers that can help him make specific prime number from 1 to t(both inclusive).
Constraints
1<=z<=10^5
1<=t<=5*10^6
Input
first line will contain an integer z, denoting the number of queries, next z lines will contain a number t.
Output
Output the answer in each single line.
Note Answer can be very large , use modulo 10^8+7.
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
