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 (1≤Q≤106). Then there will be Q lines. Each of the Q lines will contain two positive integers A (2≤A≤106) and B (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.