K-Th Root

Hasinur_ Replay of Ada Lovelace Na...
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.

Input

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

Output

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.

Sample

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

Submit

Login to submit.

Statistics

61% Solution Ratio
Jeba_1603051Earliest, Jan '20
Yasir_ArafatFastest, 0.2s
fire_tornadoLightest, 25 MB
white_negroShortest, 387B
Toph uses cookies. By continuing you agree to our Cookie Policy.