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
thanhdatmu2003: 2021-12-12 03:30:22

becareful a[n] can be long long

princemishra: 2020-10-23 11:27:37

AC In One Go

ameyanator: 2018-09-26 12:48:58

nice sieve question

maxboom321: 2018-09-20 06:55:18

Simple precalculation :D!

sonuverma: 2018-07-02 12:01:42

Pre-computation and Pre-computation :)

m2do: 2018-01-07 17:26:55

aims at optimisation

rayhan50001: 2017-08-14 00:50:35

AC In One Go. 18th.. :D dp

pratham_1: 2017-07-15 17:41:13

Awesome sieve+dp:) Ac in 3 go , dont forget to use long long answers are explosive:)

rohit9934: 2017-07-11 15:41:20

sieve+pre-computation gives :)

habibpqt619: 2017-06-30 17:35:24

weak test cases


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