Prime Factor Love

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

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