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
anuj0503: 2016-07-15 08:46:20

150th !!

shresthsoni: 2016-06-16 19:52:29

My code is working fine on codeblocks but gives SIGSEGV error, here on spoj. HELP!!

akshayvenkat: 2016-05-30 13:01:42

Precompute using Prime Sieve and O(1) retrieval B| TLE->TLE->WA->AC

manish3749: 2016-05-21 22:26:34

why is it showing run time error???

papan_97: 2016-05-16 19:08:09

got accepted using sieve and noting down the first prime divisor for each number inside sieve function...nice question though :D

Last edit: 2016-05-16 19:08:26
Ray Brish Bhanu: 2016-04-16 19:54:19

learned diff b/w declaring an array locally and globally

manas0008: 2016-03-16 21:28:27

good problem to learn application of sieve.Precomputation is necessary i think

ashu05: 2016-02-12 19:56:13

worked even with long long int!!
AC in one go =D =D

nightwolf_9197: 2016-02-02 17:06:32

easy one! my half century complete..................!!!!!!

Last edit: 2016-02-02 17:08:05
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... :)


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