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
sy_117:
20160729 19:06:45
nD here 100th completed with such a nice ques !!! modified sieve + precomputation . :)


anuj0503:
20160715 08:46:20
150th !! 

shresthsoni:
20160616 19:52:29
My code is working fine on codeblocks but gives SIGSEGV error, here on spoj. HELP!! 

akshayvenkat:
20160530 13:01:42
Precompute using Prime Sieve and O(1) retrieval B TLE>TLE>WA>AC 

manish3749:
20160521 22:26:34
why is it showing run time error??? 

papan_97:
20160516 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: 20160516 19:08:26 

Ray Brish Bhanu:
20160416 19:54:19
learned diff b/w declaring an array locally and globally


manas0008:
20160316 21:28:27
good problem to learn application of sieve.Precomputation is necessary i think 

ashu05:
20160212 19:56:13
worked even with long long int!!


nightwolf_9197:
20160202 17:06:32
easy one! my half century complete..................!!!!!!

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