# Practice on Toph

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

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

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 starts with an integer T (≤ 1000), denoting the number of test cases. Each case contains an integer n (0 ≤ n ≤ 2000000000).

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

Input | Output |
---|---|

3 10 50 100 | Case 1: 23 Case 2: 20 Case 3: 25 |

- 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

35% Solution Ratio

hafiz_samratEarliest,

NJRafiFastest, 0.0s

hafiz_samratLightest, 131 kB

zishan044Shortest, 690B

Login to submit