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
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.

Ouditchya Sinha: 2013-05-14 18:08:13

Finally AC!!! Amazing Problem Indeed. :)

[Lakshman]: 2013-03-20 19:53:48

ha..ha..Finally got AC after several TLEs...Enjoyed solving it...
@Tjandra Satria Gunawan)(曾毅昆)
A little change in Algorithm while precomputing the values and GOT AC..:)

Last edit: 2013-03-20 19:54:28
[Lakshman]: 2013-03-19 13:41:18

I am getting TLE don't know why on ideone code is giving correct output in 0.30 seconds with 100 test cases and max value(1000000)
http://ideone.com/***** edit(Tjandra): please don't spoil here
@(Tjandra Satria Gunawan)(曾毅昆)

can you check my code and help me what is wrong..
Ans(Tjandra): Your code giving correct answer but too slow, Ideone using Cube cluster, but this problem using pyramid cluster that approx 10x slower than cube..

Last edit: 2013-03-19 16:27:36
(Tjandra Satria Gunawan)(曾毅昆): 2013-03-17 14:38:59

I'm happy because I got AC in 0.00s
So I'll give you all one free case ;-)
input:
1
1000000000000000000
output:
322467033424113218863487627735401433
Computed less than 30s on my computer..
Just for info, not spamming, haha.. :-) That answer is correct..

Last edit: 2013-03-17 14:41:33

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