## 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```

## Code Examples

### #1 Code Example with Python Programming

```Code - Python Programming```

``````MAX = 500005
sigma = [0] * MAX
lp = [0] * MAX
p = [0] * MAX
pc = [0] * MAX

for i in range(2, MAX):
if lp[i] == 0:
for j in range(i, MAX, i):
if lp[j] == 0:
lp[j] = i
sigma[1] = 1
for i in range(2, MAX):
j = i / lp[i]
if j % lp[i] == 0:
p[i] = p[j]
pc[i] = pc[j] * lp[i]
else:
p[i] = j
pc[i] = lp[i]
sigma[i] = sigma[p[i]] * (pc[i] * lp[i] - 1) / (lp[i] - 1)
T = int(input())
for _ in range(T):
N = int(input())
print(sigma[N] - N)``````
Copy The Code &

Input

cmd
3
2
10
20

Output

cmd
1
8
22

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <cstdio>

using namespace std;

int main(){
int t,n,i;
int S;

scanf("%d",&t);

for(int tc=1;tc<=t;tc++){
scanf("%d",&n);

S=0;

for(i=1;i*i<n;i++)
if(n%i==0)
S+=i+n/i;

if(i*i==n) S+=i;
S-=n;

printf("%d\n",S);
}

return 0;
}``````
Copy The Code &

Input

cmd
3
2
10
20

Output

cmd
1
8
22