DIVSUM - Divisor Summation


Given a natural number n (1 ≤ n ≤ 500000), please output the summation of all its proper divisors.

Definition: A proper divisor of a natural number is the divisor that is strictly less than the number.

e.g. number 20 has 5 proper divisors: 1, 2, 4, 5, 10, and the divisor summation is: 1 + 2 + 4 + 5 + 10 = 22.

Input

An integer stating the number of test cases (equal to about 200000), and that many lines follow, each containing one integer between 1 and 500000 inclusive.

Output

One integer each line: the divisor summation of the integer given respectively.

Example

Sample Input:
3
2
10
20

Sample Output:
1
8
22

Warning: large Input/Output data, be careful with certain languages


hide comments
Darky: 2013-04-15 15:57:39

@numerix:Yeah, but again a compilation error in JAVA. :x

numerix: 2013-04-15 15:57:39

@darky1: What do you think is the reason for only a single Python 3.1 AC submission? Just use a faster language ...

Darky: 2013-04-15 15:57:39

How to get rid of TLE in python?

Yashodhan S. Katte: 2013-04-15 15:57:39

Pavel Thanks for help.

Pathan Salman Khan: 2013-04-15 15:57:39

What is the value for 4?
3 or 5?

Erben: 2013-04-15 15:57:39

What is SIGKILL? Got SIGKILL everytime :S

titangate: 2013-04-15 15:57:39

takes 0.4s for 200000 cases on my computer but got TLE :/

Pandian: 2013-04-15 15:57:39

This is totally unfair. . Got acc after including the test case for 0.But in the problem it was specified only 1 to 500000. Pls change it . . .

sandeep: 2013-04-15 15:57:39

my algo is working in O(sqrt(n)).. But still i am getting TLE..
That's because sqrt(n)*T won't fit in time. you need optimization.

Last edit: 2012-02-03 13:28:53
Ahmed Abdel Samad: 2013-04-15 15:57:39

for the test case of "1" shall it output one or zero?

Last edit: 2012-01-25 14:14:21

Added by:Neal Zane
Date:2004-06-10
Time limit:3s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Neal Zane