K-Th Root

Limits 1.5s, 512 MB

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

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


First line of the input will contain a single integer QQ (1Q1061 ≤ Q ≤ 10^6). Then there will be QQ lines. Each of the QQ lines will contain two positive integers AA (2A1062 ≤ A ≤ 10^6) and BB (1B2×1091 ≤ B ≤ 2 \times 10^9).


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


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