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!
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}$.
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$.