Just a Math Problem
Time Limit: 20000/15000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 42 Accepted Submission(s): 3
Problem Description
Little Ruins is a studious boy, recently he learned math!
Now he defines $f(k$) equal the number of prime factors in $k$, and $g(k) = 2^{f(k)}$, he want to know
$$\sum_{i = 1}^{n} g(i)$$
Please help him!
Now he defines $f(k$) equal the number of prime factors in $k$, and $g(k) = 2^{f(k)}$, he want to know
$$\sum_{i = 1}^{n} g(i)$$
Please help him!
Input
First line contains an integer $T$, which indicates the number of test cases.
Every test case contains one line with one integer $n$.
Limits
$1 \leq T \leq 50$.
$1 \leq n \leq 10^{12}$.
Every test case contains one line with one integer $n$.
Limits
$1 \leq T \leq 50$.
$1 \leq n \leq 10^{12}$.
Output
For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the result.
Because y could be very large, just mod it with $10^9 + 7$.
Because y could be very large, just mod it with $10^9 + 7$.
Sample Input
3 1 10 100
Sample Output
Case #1: 1 Case #2: 23 Case #3: 359