13241324 SUSTech Online Judge
Problem 1324 --Number Theory Battle

## 1324: 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

[Submit][Status]