Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

K-Th Root

By Hasinur_ · Limits 1.5s, 512 MB

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 NK = AB. 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. Then there will be Q lines. Each of the Q lines will contain two positive integers A and B.

1 ≤ Q ≤ 106
2 ≤ A ≤ 106
1 ≤ B ≤ 2*109

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. See sample input-output for better understanding.

Sample

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


Discussion
Statistics

59% Solution Ratio

Jeba_1603051Earliest, 2w ago

Amantu_AmirFastest, 0.3s

fire_tornadoLightest, 25 MB

mijanurShortest, 411B

Submit

Login to submit