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
---@@@----: 2015-06-08 05:36:34

Accepted after lot of TLE's...

Last edit: 2015-06-08 05:37:02
[Mayank Pratap]: 2015-06-03 05:37:35

Nice for beginners like me!!!

NEXES: 2015-06-02 14:24:40

Some Change in the Sheive and got ac!!!!

kartikay singh: 2015-05-21 10:58:32

AC in 1 go:)
BRUTE FORCE (y)

happy: 2015-05-03 17:00:26

accepted in one go!!!

Madhav: 2015-04-14 11:49:14

done!!

krish: 2015-04-11 20:29:49

brute force only:)

free mind ;): 2014-03-21 18:08:10

nice one :)

Sameer: 2014-01-02 10:21:04

@Prakhar Gupta : Make it global or static :)

The_ROCK: 2013-12-29 08:22:04

@Karan Dev : Its because for high values your recursive function eats up all the stack memory.
For more details on how recursion works, visit
http://en.wikipedia.org/wiki/Stack_overflow


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