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!

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

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

3
1
10
100

Case #1: 1
Case #2: 23
Case #3: 359