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

    Discussion

    Statistics


    35% Solution Ratio

    hafiz_samratEarliest, 1M ago

    NJRafiFastest, 0.0s

    hafiz_samratLightest, 131 kB

    zishan044Shortest, 690B

    Submit

    Login to submit

    Related Contests