UDIVSUM - The Sum of Unitary Divisors


A natural number $d$ is a unitary divisor of $n$ if $d$ is a divisor of $n$ and if $d$ and $\frac{n}{d}$ are coprime.

Let $\sigma^{*}(n)$ be the sum of the unitary divisors of $n$. For example, $\sigma^{*}(1) = 1$, $\sigma^{*}(2) = 3$ and $\sigma^{*}(6) = 12$.

Let $$S(n) = \sum_{i=1}^n \sigma^{*}(i).$$

Given $n$, find $S(n) \bmod 2^{64}$.

Input

There are multiple test cases. The first line of input contains an integer $T$ ($1 \le T \le 50000$), indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 5 \times 10^{13}$).

Output

For each test case, output a single line containing $S(n) \bmod 2^{64}$.

Example

Input:

7
1
2
3
4
5
100
100000

Output:

1
4
8
13
19
6889
6842185909

Information

There are 8 Input files.

  • Input #1: $1 \le n \le 50000$, TL=1s
  • Input #2: $1 \le T \le 1000, \ 1 \le n \le 5 \times 10^7$, TL=5s
  • Input #3: $1 \le T \le 300, \ 1 \le n \le 5 \times 10^8$, TL=5s
  • Input #4: $1 \le T \le 80, \ 1 \le n \le 5 \times 10^9$, TL=5s
  • Input #5: $1 \le T \le 30, \ 1 \le n \le 5 \times 10^{10}$, TL=10s
  • Input #6: $1 \le T \le 10, \ 1 \le n \le 5 \times 10^{11}$, TL=10s
  • Input #7: $1 \le T \le 3, \ 1 \le n \le 5 \times 10^{12}$, TL=10s
  • Input #8: $T=1, \ 1 \le n \le 5 \times 10^{13}$, TL=10s

My unoptimized C++ solution runs in 8.9 sec (total time). And with some constant optimization, now my C++ solution runs in 1.03 sec (total time).


hide comments
zimpha: 2018-01-18 17:28:55

@[Rampage] Blue.Mary, I don't think so. It just replaces uint64_t with uint128_t, and it's better to focus more on the method.

[Rampage] Blue.Mary: 2018-01-18 11:14:50

It's more interesting if the problem doesn't require the answer to modulo 2^64 :P


Added by:zimpha
Date:2018-01-17
Time limit:1s-10s
Source limit:10240B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All