AFS3  Amazing Factor Sequence (hard)
Let $s_1(n)$ be the sum of positive proper divisors of $n$.
For example, $s_1(1) = 0$, $s_1(2) = 1$ and $s_1(6) = 6$.
Let $$S(n) = \sum _{i=1}^n s_1(i).$$
Given $N$, find $S(N)$.
Input
First line contains $T$ ($1 \le T \le 10^5$), the number of test cases.
Each of the next $T$ lines contains a single integer $N$. ($1 \le N < 2^{63}$)
Output
For each number $N$, output a single line containing $S(N)$.
Example
Input
6 1 2 3 10 100 1000000000000000000
Output
0 1 2 32 3249 322467033424113218863487627735401433
Information
There are 6 Input files.
 Input #1: $1 \le N \le 10^5$, TL = 2s.
 Input #2: $1 \le T \le 60,\ 1 \le N \le 10^{15}$, TL = 10s.
 Input #3: $1 \le T \le 25,\ 1 \le N \le 10^{16}$, TL = 10s.
 Input #4: $1 \le T \le 10,\ 1 \le N \le 10^{17}$, TL = 10s.
 Input #5: $1 \le T \le 5,\ 1 \le N \le 10^{18}$, TL = 10s.
 Input #6: $1 \le T \le 2,\ 1 \le N < 2^{63}$, TL = 10s.
My C++ solution runs in about 0.85 seconds for each Input #2  #6.
Note
 Probably, $O(\sqrt{n})$ solutions will not pass.
 Intended solutions have a running time of about $O(n^{1/3} \log n)$.
 Time limits are somewhat strict.
 The answer can be $\ge 2^{64}$.
 DIVCNT1 is a little easier than this.
hide comments
Min_25:
20190321 13:40:31
@liouzhou_101


liouzhou_101:
20190320 06:56:30
@Min_25


dacin21:
20171212 10:02:16
@Min_25


Min_25:
20171212 08:32:39
@dacin21

Added by:  Min_25 
Date:  20171019 
Time limit:  2s10s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  AFS2 