Limits 1s, 512 MB

After the fight between Mysterio and Spider-Man, Mysterio revealed Spider-man’s identity to the world. Now everyone knows that Peter Parker is Spider-Man. That’s why he is receiving unwanted attention which is affecting him and his close friend’s personal life. So Peter wants everyone to forget about his superhero identity. That’s why he visited Doctor Strange for help. After hearing his problem, Strange agreed to help him by casting a forbidden spell. But something went wrong and Strange blamed Spider-Man for his dual identity and a fight between those two superheroes began.

As the fight goes on, Doctor Strange uses a spell to put Spider-Man in a trap where Strange vanishes from one point and comes out from another to beat Spider-Man. Because of the peter tingle, Spider-Man was barely able to defend himself. Fortunately, a communication between You and Spider-Man is still connected and he wants your help to predict from which point Strange will emerge. After analyzing Strange's movement, you find that if his last attack was coming from point AA and Point BB, then his next attack will come from a point which is divisible by both AA and BB and the value of the point is positive and as small as possible.

Now write a program that will help you to predict the next attack Point of Doctor Strange, if Point A and Point B is given.

Input

The first line will be a single integer TT indicating the number of test cases. The following T lines will contain two integers AA, BB separated by spaces.

1T1021 ≤ T ≤10^2

1A,B1041 ≤ A , B ≤ 10^4

Output

You have to output T lines in format “Case X: Y”(without quotes) where XX is the number of test case starting from 11 and YY is the smallest positive number divisible by both A and B. It is guaranteed that the result will not be greater than 10610^6.

Sample

InputOutput
3
2 6
1 616
10 10
Case 1: 6
Case 2: 616
Case 3: 10

Submit

Login to submit.

Statistics

69% Solution Ratio
abu_fayeemEarliest, Mar '22
user.404682Fastest, 0.0s
abu_fayeemLightest, 131 kB
Nusab19Shortest, 77B
Toph uses cookies. By continuing you agree to our Cookie Policy.