400915: GYM100283 I Bakkar In Zanzibar

Congratulations; Bakkar has just passed his interview and got the job. He is now going to call Maymona’s Father to arrange with him when they can make their wedding and finally get married. But wait a second, he just got an email from the company stating that he will have to travel to Zanzibar to complete a training on the project they are going to develop. Unfortunately Bakkar has to postpone his marriage for one more month. His trip will be next week and he is already packing up but this time he has already arranged everything with Maymona’s father and they agreed on the date of their wedding. By the way you are invited ;).

Bakkar has just arrived at the airport of Zanzibar and wanted to exchange some money for his transportation. He discovered a very strange thing about their money, they have banknotes only in the form of fractions of their currency ZPound. He asked Koromba (his trip guide) about that and he explained that all banknotes in Zanzibar are made of fractions of ZPound in the form a/b where 0 < a < b and 2  ≤  b  ≤  13.

Bakkar arrived at the hotel to have some rest and to explore Zanzibar on the next day as it's a weekend in Zanzibar. Bakkar woke up and decided to go shopping to buy some gifts for Maymona.

While he was shopping he noticed that all prices are all less than 1 ZPound. He also noticed that some of the prices cannot be generated by the available banknotes. Later, he was informed that when the price cannot be generated by the banknotes, the convention is that the customer pays the amount of money that makes the minimum absolute difference to the original price (the buyer can actually pay more or less than the original price). Formally, if the price is X/Y ZPound, the customer will end up paying S ZPound such that |S - X/Y| is minimum. When the customer pays more than the original price, that is considered tips to the salesman. And when he pays less than the original price, that is considered a courtesy by the shop to the customer.

Bakkar got confused by that; so he decided to develop a mobile app to help him with this task. For a given price X/Y, the mobile app should output the minimum absolute difference between what should be paid and the given price.

Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1  ≤  T  ≤  10⁵). Followed by T test cases, each test case will be 2 integers X and Y representing an item that has a price of X/Y ZPound, where X < Y and (0  ≤  X < Y ≤  10⁵).

For each test case print a single line containing "Case n:" (without the quotes) where n is the test case number (starting from 1) followed by a single space, then a fraction of the form a/b representing the minimum absolute difference between what should be paid and the given price where gcd(a,b) = 1.

The greatest common divisor "gcd" of two or more integers (at least one of which is not zero), is the largest positive integer that divides the numbers without a remainder. For example, the gcd of 8 and 12 is 4.

3
13 17
33 47
11 21

Case 1: 1/42840
Case 2: 1/109980
Case 3: 1/12012