Migrated from Lutece 1503 J

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

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 wants to know

Please help him!

Input

First line contains an integer $T$ ($1\le T\le 50$), which indicates the number of test cases.

Every test case contains one line with one integer $n$ ($1\le n\le 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$.

Samples

3
1
10
100

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

Resources

第二届中国大学生程序设计竞赛 杭州站（CCPC 2016 Hangzhou Site）