APS2 - Amazing Prime Sequence (hard)

This problem is a harder version of APS.

 

Let $f(n)$ be the smallest prime factor of $n$. For example, $f(2) = 2,\ f(4) = 2$ and $f(35) = 5$.

The sequence $S(n)$ is defined for all positive integers as follows:

  • $S(1) = 0$
  • $S(n) = S(n-1) + f(n)$ (if $n \ge 2$)

Given $N$, find $S(N)$ modulo $2^{64}$.

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

Output

For each integer $N$, output a single line containing $S(N)$ modulo $2^{64}$.

Example

Input

5
1
4
100
1000000
1000000000000

Output

0
7
1257
37568404989
7294954823202325427

Explanation for Input

- $S(4) = 2 + 3 + 2 = 7$

- $S(10^{12}) = 18435592284459044389811 \equiv 7294954823202325427 \pmod{2^{64}}$

Information

There are 6 Input files.

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

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

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

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

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

- Input #5: $T = 1$, $1 \le N \le 1234567891011$, TL = 20s.

My solution runs in 5.36 sec. (total time)

Source Limit is 8 KB.


Added by:Min_25
Date:2014-06-05
Time limit:1s-20s
Source limit:8192B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:APS

hide comments
2016-04-15 05:18:17 [Rampage] Blue.Mary
The source limit and time limit are both reasonable (twice of my ugly code's source length and running time) for solving this problem. Thanks to min_25 for setting those constraints carefully.

Last edit: 2016-04-15 05:19:29
2015-01-28 08:40:19 abdou_93
not (hard).for more sense (impossible)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.