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.
3 10 50 100
Case 1: 23 Case 2: 20 Case 3: 25