DIVCNT1 - Counting Divisors


Let $\sigma_0(n)$ be the number of positive divisors of $n$.

For example, $\sigma_0(1) = 1$, $\sigma_0(2) = 2$ and $\sigma_0(6) = 4$.

Let $$S_1(n) = \sum _{i=1}^n \sigma_0(i).$$

Given $N$, find $S_1(N)$.

Input

First line contains $T$ ($1 \le T \le 100000$), 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_1(N)$.

Example

Input

5
1
2
3
10
100

Output

1
3
5
27
482

Explanation for Input

- $S_1(3) = \sigma_0(1) + \sigma_0(2) + \sigma_0(3) = 1 + 2 + 2 = 5$

Information

There are 6 input files.

- Input #1: $1 \le N \le 100000$, TL = 2s.

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

- Input #3: $1 \le T \le 60,\ 1 \le N \le 10^{16}$, TL = 15s.

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

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

- Input #6: $1 \le T \le 5,\ 1 \le N < 2^{63}$, TL = 15s.

My C++ solution runs in about 1.3 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)$.
  • The answer can be $\ge 2^{64}$.

hide comments
userhacker_1: 2018-03-16 16:15:28

thanks good problem ;\

Last edit: 2018-03-16 19:04:23
Min_25: 2017-11-09 04:43:17

@Blue.Mary
Its approach is a little different from mine. So, I'm not sure it helps to prove the complexity ...

[Rampage] Blue.Mary: 2017-11-08 02:31:15

Maybe this paper helps? https://arxiv.org/abs/1206.3369.

Min_25: 2017-11-07 23:31:46

@dacin21:
Thank you. (Although, the original idea comes from the forum of Project Euler 540)

Sorry, I don't have a proof (and the above forum doesn't either).

The convex full of this hyperbola seems have $\Theta(n^{1/3} \log{n})$ sloops $(O(n^{1/3})$ slopes for each interval $\left[\frac{\sqrt{n}}{2^{k+1}}, \frac{\sqrt{n}}{2^k}\right]$, $k = 0, 1, \ldots)$. So, I can only says that my and your approach (probably) has a complexity of $\Omega(n^{1/3} \log{n})$.

Last edit: 2017-11-07 23:32:14
dacin21: 2017-11-07 21:16:12

@Min_25 This is a really beautiful problem, thanks a lot for posting it.
Do you have a proof/argument why the solution (from submission 20543216) runs in O(n^{~1/3})?


Added by:Min_25
Date:2015-12-30
Time limit:2s-15s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY