RXD is a good mathematician.
One day he wants to calculate:
$$\sum_{i = 1}^{n^k}{\mu^2(i) \times \lfloor \sqrt{\frac{n^k}{i}} \rfloor}$$
output the answer module $10^9+7$.
$1\leq n, k\leq 10^{18}$
$$\mu(n) = 1 (n = 1)$$
$$\mu(n) = (-1)^k (n = p_1p_2\dots p_k)$$
$$\mu(n) = 0(otherwise)$$
$p_1,p_2,p_3\dots p_k$ are different prime numbers

There are several test cases, please keep reading until EOF.
There are exact 10000 cases.
For each test case, there are 2 numbers $n, k$.

For each test case, output "Case #x: y", which means the test case number and the answer.