Problem M: Number Theory Battle

Problem M: Number Theory Battle

Time Limit: 5 Sec  Memory Limit: 512 MB
Submit: 5  Solved: 3
[Submit][Status][Web Board]

Description

LowbieH and Wtd are both math lovers. One day, LowbieH receives a letter of challenge from Wtd. The letter says, "Let's have a competition on number theory!" Here's the problem of their race:


Define \(f(n)=\sum_{d|n}d[gcd(d,\frac{n}{d})==1]\), for given integer \(n\), please calculate \(S(n)=\sum_{i=1}^n f(i)\) and print the result mod \(10^9+7\).


LowbieH solves the problem easily, while Wtd is still puzzling over it. Can you help Wtd to figure it out?

Input

The first line contains an integer \(T(1\leq T \leq 10)\), denoting the number of test cases.


For each test case, there's an integer \(n(1\leq n \leq 10^{12})\).

Output

For each test case, print one line an integer denoting the answer.

Sample Input

3
1
10
100

Sample Output

1
76
6889

HINT

[Submit][Status]