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
chicku: 2013-02-15 11:33:23

what it is doing in classical problem. just move it to tutorial man!!!

Ankit Paharia: 2013-02-15 11:33:23

very nice problem ... !!!

:D: 2013-02-15 11:33:23

Alex, what do you mean by bad input? Do you think there are some errors or is it simply not using extreme values for N?

(Tjandra Satria Gunawan)(曾毅昆): 2013-02-15 11:33:23

first place :-D
But I feel my algo still not the optimal one
EDIT: Now, I don't need long long integer anymore to solve this problem ;-) T=100 is small...
@Problem Seter: Nice problem ;-) I like it, could you change the cluster to pyramid? I think pyramid cluster is better for speed comparsion..

Last edit: 2013-02-15 07:08:42
abdelkarim: 2013-02-15 11:33:23

nice one .

Last edit: 2013-02-15 05:07:56
Ehor Nechiporenko: 2013-02-15 11:33:23

APS: Amazing problem seriously!

Last edit: 2013-02-14 20:44:59

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