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 .