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
@@@:
20150608 05:36:34
Accepted after lot of TLE's... Last edit: 20150608 05:37:02 

[Mayank Pratap]:
20150603 05:37:35
Nice for beginners like me!!! 

NEXES:
20150602 14:24:40
Some Change in the Sheive and got ac!!!!


kartikay singh:
20150521 10:58:32
AC in 1 go:)


happy:
20150503 17:00:26
accepted in one go!!! 

Madhav:
20150414 11:49:14
done!! 

krish:
20150411 20:29:49
brute force only:) 

free mind ;):
20140321 18:08:10
nice one :)


Sameer:
20140102 10:21:04
@Prakhar Gupta : Make it global or static :) 

The_ROCK:
20131229 08:22:04
@Karan Dev : Its because for high values your recursive function eats up all the stack memory.

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 