G. Good Number
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Alex loves numbers.

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.

Example
Input
2
233 1
233 2
Output
Case #1: 233
Case #2: 43