AFS - Amazing Factor Sequence

no tags 

Bhelu is the classmate of Bablu who made the Amazing Prime Sequence .

He felt jealous of his classmate and decides to make his own sequence. Since he was not very imaginative, he came up with almost the same definition just making a difference in f(n):

  • a[0] = a[1] = 0.
  • For n > 1, a[n] = a[n - 1] + f(n), where f(n) is the sum of positive integers in the following set S.
  • S = {x | x < n and n % x = 0}.

Now, Bablu asked him to make a code to find f(n) as he already had the code of his sequence. So, Bhelu asks for your help since he doesn't know Programming. Your task is very simple, just find a[n] for a given value of n (< 10^6).

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 positive integer N. (1 < N < 10^6).

Output

Single line containing a[n] i.e. n-th number of the sequence for each test case.

Example

Input:
3
3
4
5

Output:
2
5
6

Explanation

f(2) = 1 {1}
f(3) = 1 {1}
f(4) = 3 {1, 2}
f(5) = 1 {1}

hide comments
pratyush2013: 2016-07-20 19:35:44

this problem is easy if u r not overconfident...please focus more on problem statement

Last edit: 2016-07-20 19:36:13
darkchocolate: 2016-06-14 19:24:06

@Ankit got accepted after declaring array globally. Thanks!

godfrey_17897: 2016-02-10 18:00:06

modify sieve and you are done !!!!

GAURAV CHANDEL: 2016-01-31 14:25:49

I love precalculations....

shantanu tripathi: 2015-09-17 19:28:33

o(n) also got accpted...hehe

vedang: 2015-08-04 23:19:19

DO NOT USE INT.
It costed me many many WAs :(

Piyush Kumar: 2015-05-21 16:49:04

I hate precalculations

Ankit Sultana: 2015-04-22 14:12:38

Use long long and make array global

Last edit: 2015-04-22 14:12:54
karan: 2015-04-20 21:55:05

easy one :)

TIGM: 2014-06-25 13:03:30

a missing 0 resulted in a lot of wrong answer.


Added by:c[R]@zY f[R]0G
Date:2013-03-15
Time limit:0.457s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64