407347: GYM102769 G Good Number

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$$$ ?

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)$$$.

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.

2
233 1
233 2

Case #1: 233
Case #2: 43