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

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

hide comments
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... :)
2016-01-21 06:27:53 chandan kumar
Easy problem if you use the concept of sieve of Eratosthenes
2016-01-15 17:51:14 minhthai
nice for beginner like me :)
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
2015-08-26 21:48:34
easy problem,done using sieve,,,,
2015-08-16 18:46:16 [Mayank Pratap]
@dushyant ...no need of unsigned if using sieve
2015-08-11 14:06:22
not reading @dushyant comment costed me 1 WA

Last edit: 2015-08-11 14:09:50
2015-07-30 22:53:33 Satyam Mishra
ACed..
Sieve + DP :)
2015-07-30 09:49:31 Dushyant Singh
Those who are getting WA change everything to unsigned long long, same for those who are getting TLE. :-)
2015-07-25 05:28:56 ANIKET
rojers's algorithms rocks......ac in 1/2 go...... only one line code :P :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.