{"raw_statement":[{"iden":"statement","content":"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 ;).\n\n*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.\n\n *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*.\n\nWhile 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.\n\n*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.\n\nYour 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*  ≤  105). 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* ≤  105).\n\nFor 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.\n\nThe 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.\n\n"},{"iden":"input","content":"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*  ≤  105). 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* ≤  105)."},{"iden":"output","content":"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."},{"iden":"examples","content":"Input313 1733 4711 21OutputCase 1: 1/42840Case 2: 1/109980Case 3: 1/12012"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $, let $ \\frac{X_k}{Y_k} \\in \\mathbb{Q} $ be the given price, where $ 0 \\le X_k < Y_k \\le 10^5 $ and $ Y_k \\ge 1 $.  \n\nLet $ \\mathcal{F} = \\left\\{ \\frac{a}{b} \\in \\mathbb{Q} \\,\\middle|\\, 0 < a < b,\\ 2 \\le b \\le 13 \\right\\} $ be the set of available banknotes.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 10^5 $  \n2. For each $ k $: $ 0 \\le X_k < Y_k \\le 10^5 $, $ Y_k \\ge 1 $  \n\n**Objective**  \nFor each test case $ k $, compute:  \n$$\n\\min_{\\frac{a}{b} \\in \\mathcal{F}} \\left| \\frac{a}{b} - \\frac{X_k}{Y_k} \\right|\n$$  \nand output the result as a reduced fraction $ \\frac{a^*}{b^*} $, where $ \\gcd(a^*, b^*) = 1 $.","simple_statement":"Given a price X/Y ZPound, find the smallest absolute difference between X/Y and any fraction a/b where 0 < a < b ≤ 13. Output the difference as a reduced fraction a/b.","has_page_source":false}