You will be given queries. In each query, you will be given two positive integers and . You have to find such positive integer that there exist a positive integer and . If there exists multiple possible values for , take the maximum of them.
For example, if and then has to be 16.
First line of the input will contain a single integer (). Then there will be lines. Each of the lines will contain two positive integers () and ().
For each test case print one line "Case #x: y" without quotations where is the query number and is the answer to the query described in the statement.
3 2 4 27 3 5 2
Case #1: 4 Case #2: 9 Case #3: 2