## GCDEX2 - GCD Extreme (hard)

This problem is a harder version of GCDEX.

Let

$$G(n) = \sum _{i=1}^{n} \sum _{j=i+1}^{n} \gcd(i, j).$$

For example, $G(1) = 0$, $G(2) = \gcd(1, 2) = 1$, $G(3) = \gcd(1, 2) + \gcd(1, 3) + \gcd(2, 3) = 3$.

Given $N$, find $G(N)$ modulo $2^{64}$.

### Input

First line of contains $T$ ($1 \le T \le 10000$), the number of test cases.

Each of the next $T$ lines contains a single integer $N$. ($1 \le N \le 235711131719$)

### Output

For each number $N$, output a single line containing $G(N)$ modulo $2^{64}$.

### Example

#### Input

5141001000000100000000000

#### Output

071301540716286739125482289417216306300

### Explanation for Input

- $G(4) = \gcd(1, 2) + \gcd(1, 3) + \gcd(1, 4) + \gcd(2, 3) + \gcd(2, 4) + \gcd(3, 4) = 7$.

- $G(10^{11}) = 75710919967921216138364 \equiv 5482289417216306300 \pmod{2^{64}}$.

### Information

There are 7 Input files.

- Input #0: $1 \le T \le 10000$, $1 \le N \le 10000$, TL = 1s.

- Input #1: $1 \le T \le 1000$, $1 \le N \le 10^{7}$, TL = 20s.

- Input #2: $1 \le T \le 200$, $1 \le N \le 10^{8}$, TL = 20s.

- Input #3: $1 \le T \le 40$, $1 \le N \le 10^{9}$, TL = 20s.

- Input #4: $1 \le T \le 10$, $1 \le N \le 10^{10}$, TL = 20s.

- Input #5: $1 \le T \le 2$, $1 \le N \le 10^{11}$, TL = 20s.

- Input #6: $T = 1$, $1 \le N \le 235711131719$, TL = 20s.

My solution runs in 10.7 sec. (total time)

Source Limit is 10 KB.

 Ishan: 2023-03-28 08:35:17 Is $O(N^{3/4})$ enough? Last edit: 2023-03-28 08:35:38 boomminecraft8: 2019-02-09 01:26:42 As the tag shows, use Dirichlet convolution. Also there's a related problem on project euler 625 siyuan: 2018-12-09 12:37:13 This problem is so difficult. If anyone have solved it, please give me some ideas. Thanks a lot! Last edit: 2018-12-09 12:43:48