Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.
Alex thinks that a positive integer $$$x$$$ is good if and only if $$$\lfloor \sqrt[k]{x} \rfloor$$$ divides $$$x$$$.
Can you tell him the number of good positive integers which do not exceed $$$n$$$ ?
Input
The first line of the input gives the number of test cases, $$$T\ (1 \le T \le 10)$$$. $$$T$$$ test cases follow.
For each test case, the only line contains two integers $$$n$$$ and $$$k\ (1 \le n,k \le 10^9)$$$.
Output
For each test cases, output one line containing "Case #x: y", where $$$\texttt{x}$$$ is the test case number (starting from $$$1$$$), and $$$\texttt{y}$$$ is the answer.