K-Th Root

You will be given $Q$ queries. In each query, you will be given two positive integers $A$ and $B$. You have to find such positive integer $K$ that there exist a positive integer $N$ and $N^K = A^B$. If there exists multiple possible values for $K$, take the maximum of them.

For example, if $A = 2$ and $B = 16$ then $K$ has to be 16.

Input

First line of the input will contain a single integer $Q$ ($1 ≤ Q ≤ 10^6$). Then there will be $Q$ lines. Each of the $Q$ lines will contain two positive integers $A$ ($2 ≤ A ≤ 10^6$) and $B$ ($1 ≤ B ≤ 2 \times 10^9$).

Output

For each test case print one line "Case #x: y" without quotations where $x$ is the query number and $y$ is the answer to the query described in the statement.

Sample

Input	Output
3 2 4 27 3 5 2	Case #1: 4 Case #2: 9 Case #3: 2