# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Prime Factor Love

By mamunor.rashid · Limits 5s, 512 MB

Mr. Peter loves math lessons very much. Peter wants to get a good mark for math. For that , his math teacher, gave him a new task. Peter solved the task immediately. Can you?

The equation X of integer n, there X is Sum of all actual divisor from 1 to n.

``````                         X = SOAD(1) +SOAD(2)+..............+SOAD(n)
``````

Here SOAD is defined sum of actual divisor of integer n. Actual divisor means the divisors of n without 1 and n.

``````For example, SOAD(10) = 2+5 = 7
``````

Given the value of n, As X can be rather large, print (sum of prime factor of (X % 1000009))%1000009.

## Input

Input starts with an integer T (≤ 1000), denoting the number of test cases. Each case contains an integer n (0 ≤ n ≤ 2000000000).

## Output

For each case, print the case number and the result as remainder after dividing it by number 1000009.

## Sample

InputOutput
```3
10
50
100
```
```Case 1: 23
Case 2: 20
Case 3: 25
```

# Explanation

• 1 = 1=0
• 2 = 1 ,2 =0
• 3 = 1,3 =0
• 4 = 1,2 ,4 = 2= 2
• 5 = 1,5 = 0
• 6 = 1,2,3,6= 2+3 = 5
• 7 = 1, 7 = 0
• 8 = 1,2,4,8 = 2+4 = 6
• 9 = 1,3,9 = 3 =3
• 10 = 1,2,5,10 = 2+5 = 7
• SOAD = (0+0+0+2+0+ 5+0 + 6 +3 + 7) = (23%1000009)=23
• Sum of prime factor of 23 = (23%1000009)=23

### Statistics

35% Solution Ratio

hafiz_samratEarliest, 3M ago

NJRafiFastest, 0.0s

hafiz_samratLightest, 131 kB

zishan044Shortest, 690B

### Submit 