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
karan_dev:
20130815 10:36:57
my code works for n=10000, but not for , n=100000 or above. I checked 'smallest prime' function, it is working good for n=100000 or above. help. 

Bhagwat:
20130604 02:48:31
nice problem..:) 

Abhishek Mishra:
20130425 11:08:27
should be moved to the tutorial section... 

Eduardo Nunes:
20130418 21:56:31
nice one :D 

johri:
20130219 09:25:25
Amazing ..:)) 

Aditya Pande:
20130217 04:58:46
i guess the test cases are randomly generated. The supposedly faster code working slowly...? 

chicku:
20130216 21:34:27
@abdelkarim ya man did it before the question was there on spoj 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20130215 20:15:28
@Ehor Nechiporenko: Your memory usage give me more idea to optimize my solution ;) Thanks, haha... 

Alex Anderson:
20130215 16:15:36
The number 11,000,000 was in the input, but it seems to have been fixed now.


abdelkarim:
20130215 12:58:30
@chicku

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 