SP19985 GCDEX2 - GCD Extreme (hard)

This problem is a harder version of [GCDEX](/problem/SP3871). 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} $.

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 $ )

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