DIVCNT2 - Counting Divisors (square)

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_2(n) = \sum _{i=1}^n \sigma_0(i^2).$$

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

Input

First line 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 10^{12}$)

Output

For each number $N$, output a single line containing $S_2(N)$.

Example

Input

512310100


Output

147481194

Explanation for Input

- $S_2(3) = \sigma_0(1^2) + \sigma_0(2^2) + \sigma_0(3^2) = 1 + 3 + 3 = 7$

Information

There are 6 Input files.

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

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

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

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

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

- Input #6: $T = 1,\ 1 \le N \le 10^{12}$, TL = 20s.

My C++ solution runs in 5.3 sec. (total time)

Source Limit is 6 KB.

 < Previous 1 2 Next > userhacker_1: 2018-03-15 13:20:41 for exmple we can get Divisor Summatory Function in O(n​1/3​​logn)(DIVCNT1) instead O(√​n​​​) .... it improve time? (Re) Yes for some ranges. Last edit: 2018-03-15 13:44:25 userhacker_1: 2018-03-15 10:53:45 wow. how some user solved it in 3 sec? or they solved partially? (Re) Their solutions solved all. There are various solutions for this problem. Last edit: 2018-03-15 13:15:35 userhacker_1: 2018-03-15 10:50:06 what is you mean from total time? time sum of all input? (Re) Yes. Last edit: 2018-03-15 13:04:19 [Lakshman]: 2018-01-25 07:55:42 Thanks, @Min_25 for clarification. Just to confirm is it about my Submission-ID 21047354. (Re) $D(n/i)$ runs in $O(\sqrt{n/i})$ time. So, the same argument can be applied. Last edit: 2018-01-26 09:12:50 Min_25: 2018-01-25 07:05:54 @[Lakshman]: It is not $O(\sqrt{n})$ but $O(n^{2/3})$ since $\int_{1}^{\sqrt[3]{n}} \sqrt{n/x}\, dx \in \Theta(\sqrt{n} \cdot n^{1/6}) = \Theta(n^{2/3})$. Last edit: 2018-01-25 07:06:44 [Lakshman]: 2018-01-25 06:48:30 @Min_25 Recently I come up with some sort of $O(\sqrt{n})$,and it is working fine here as well.See 21047354, although My old solution is $O(n^{2/3})$, I am surprised to see both are producing the result in approx same time. Last edit: 2018-01-25 11:30:24 cabbby: 2016-05-17 03:00:55 @Min_25 Could I know your email? (Re: Min_25) Why ?? Last edit: 2016-05-18 07:45:54 hemant kumar: 2016-01-17 16:15:03 please provide tutorial for this problem Fionsel: 2014-10-19 11:09:53 Is it possible to give a one or more test cases of large numbers? I keep getting WA whereas I've verified (by brute force) my algorithm for numbers up to 1000 to be correct. (Re: Min_25) No other test cases are provided. Please check your code carefully. Got a stupid int^3 does not fit in a long bug. Fixed and got AC now. Last edit: 2014-10-14 02:01:07 wisfaq: 2014-10-19 11:09:53 probably something like the following would cure precision issues: function icbrt(x): res=int(cbrt(x)) while res*res*resx:res-=1 return res