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)=2f(k), he want to know
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.
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 109+7.
Case #1: 1
Case #2: 23
Case #3: 359