APS - Amazing Prime Sequence


Bablu is very fond of Series and Sequences...

After studying Fibonacci Series in Class IX, he was impressed and he designed his own sequence as follows...

a[0] = a[1] = 0 

For n > 1, a[n] = a[n - 1] + f(n), where f(n) is smallest prime factor of n.

He is also very fond of programming and thus made a small program to find a[n], but since he is in Class IX, he is not very good at programming. So, he asks you for help. Your task is to find a[n] for the above sequence....

Input

Your code will be checked for multiple Test Cases.

First Line of Input contains T (<= 100), the number of Test Cases.

Next T lines contain a single number N. (1 < N < 10^7).

Output

Single line containing a[n] i.e. nth number of the sequence for each test case.

Example

Input:
3
2
3
4

Output:
2
5
7

hide comments
ANKIT JAIN: 2017-05-09 20:44:39

Nice problem ..

arijit pande: 2017-04-06 20:51:56

Awesome optimisation problem.

lonelybanboo: 2017-03-30 08:04:34

And if you use 64 bit signed integers, remember to use "%lld" instead of "%d"......

stranger77: 2017-02-08 04:44:14

My 50th On spoj

karthik_vg: 2016-12-31 17:06:13

Last edit: 2016-12-31 17:08:52
kira28: 2016-12-23 21:56:38

AC in one go!!! XD XD
Another sieve problem:)
#1 on ranks

dwij28: 2016-08-21 15:17:31

Answer for 10000000 is 3203714961609 which is greater than the limit of a 32 bit signed integer. You must use long long, cost me a WA.

iharsh234: 2016-07-31 11:07:56

when legends copy http://www.spoj.com/problems/APS2/
_/\_

nonushikhar: 2016-07-30 21:26:41

very easy;)

sy_117: 2016-07-29 19:06:45

nD here 100th completed with such a nice ques !!! modified sieve + precomputation . :)


Added by:c[R]@zY f[R]0G
Date:2013-02-14
Time limit:1s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64