Just a Math Problem

Time Limit: 20000/15000 MS (Java/Others)

Memory Limit: 262144/262144 K (Java/Others)

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

Sample Input

3 1 10 100

Sample Output

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

Hint

liuyiding

Source

2016年中国大学生程序设计竞赛(杭州)

提交代码