LCMSUMH - LCM Sum(Hard)

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

Added by:[Lakshman]
Date:2014-11-02
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:LCMSUM

hide comments
2019-04-08 02:59:16
Is there any better solution that do not need Pollard's Rho algorithm?

==(Lakshman)==> I don't know if there is any other solution apart from factoring it.

Last edit: 2019-04-12 19:02:04
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.