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
ameyanator:
20180926 12:48:58
nice sieve question 

maxboom321:
20180920 06:55:18
Simple precalculation :D! 

sonuverma:
20180702 12:01:42
Precomputation and Precomputation :) 

m2do:
20180107 17:26:55
aims at optimisation 

rayhan50001:
20170814 00:50:35
AC In One Go. 18th.. :D dp


pratham_1:
20170715 17:41:13
Awesome sieve+dp:) Ac in 3 go , dont forget to use long long answers are explosive:) 

rohit9934:
20170711 15:41:20
sieve+precomputation gives :) 

habibpqt619:
20170630 17:35:24
weak test cases


viratian_070:
20170626 21:17:09
use long long int...very easy


Shubham Jadhav:
20170512 07:48:02
Use long long. cost me 1 WA :) 
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 