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
ashiq_iqbal: 2016-01-22 18:20:01

When will you mark the multiple of the primes...on that time you can store the prime of the multiples in the multiples... Hope it helps to avoid TLE... :)

chandan kumar: 2016-01-21 06:27:53

Easy problem if you use the concept of sieve of Eratosthenes

minhthai: 2016-01-15 17:51:14

nice for beginner like me :)

bhavya16: 2015-11-11 10:30:51

Please help....my code is running fine in code blocks but in Spoj it is giving Compilation error and sometimes runtime error
http://www.spoj.com/submit/APS/id=15596326

saini428: 2015-08-26 21:48:34

easy problem,done using sieve,,,,

[Mayank Pratap]: 2015-08-16 18:46:16

@dushyant ...no need of unsigned if using sieve

anuveshkothari: 2015-08-11 14:06:22

not reading @dushyant comment costed me 1 WA

Last edit: 2015-08-11 14:09:50
Satyam Mishra: 2015-07-30 22:53:33

ACed..
Sieve + DP :)

Dushyant Singh: 2015-07-30 09:49:31

Those who are getting WA change everything to unsigned long long, same for those who are getting TLE. :-)

ANIKET: 2015-07-25 05:28:56

rojers's algorithms rocks......ac in 1/2 go...... only one line code :P :)


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