# 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)$$

## 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

liuyiding

## Source

2016年中国大学生程序设计竞赛（杭州）