GCDEX2 - GCD Extreme (hard)


This problem is a harder version of GCDEX.

Let

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

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

Given NN, find G(N)G(N) modulo 2642^{64}.

Input

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

Each of the next TT lines contains a single integer NN. (1N2357111317191 \le N \le 235711131719)

Output

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

Example

Input

5
1
4
100
1000000
100000000000

Output

0
7
13015
4071628673912
5482289417216306300

Explanation for Input

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

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

Information

There are 7 Input files.

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

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

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

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

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

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

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

My solution runs in 10.7 sec. (total time)

Source Limit is 10 KB.


hide comments
Ishan: 2023-03-28 08:35:17

Is O(N3/4)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

Added by:Min_25
Date:2014-06-06
Time limit:1s-20s
Source limit:10240B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:GCDEX