One day Lucky was trying to solve the famous problem LCMSUM. Given n, calculate the sum LCM(1,n) + LCM(2,n) + .. + LCM(n,n), where LCM(i,n) denotes the Least Common Multiple of the integers i and n. After solving this awesome problem Lucky is trying to find out an efficient algorithm for large numbers and you know Lucky is not good at solving hard problems and need your help. As you know answer can be very big print answer modulo 10^9+7. Can you help Lucky again?

Input

The first line contains T (T < 1000) the number of test cases. Each of the next T lines contain an integer n (n <= 10^18).

Output

Output T lines, one for each test case, containing the required sum.

Example

Sample Input:
3
1
2
5

Sample Output:
1
4
55