시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 72 29 18 40.909%

문제

무한 유리수 트리는 완전 이진 트리이며, 다음과 같이 정의된다.

  • 루트는 1/1이다.
  • p/q의 왼쪽 자식은 p/(p+q)이다.
  • p/q의 오른쪽 자식은 (p+q)/q이다.

트리의 첫 세 층은 아래와 같이 구성된다.

이 무한 유리수 트리를 레벨 오더로(그림에서는 화살표 방향) 순회하여 얻어지는 수들을 나열하면 유리수 수열 F(n)을 얻을 수 있다. 첫 몇 개의 항은 아래와 같다.

F(1) = 1/1, F(2) = 1/2, F(3) = 2/1, F(4) = 1/3, F(5) = 3/2, F(6) = 2/3, …

입력으로 기약분수 p/q가 주어지면 F(n)에서 주어진 유리수의 다음 수가 무엇인지 찾는 프로그램을 작성하여라.

즉, F(n)=p/q일 때 F(n+1)을 찾으면 된다.

입력

첫 줄에 테스트 케이스의 수 P가 주어진다. (1 ≤ P ≤ 1000)

각 테스트 케이스마다 테스트 케이스의 번호와 기약분수 하나가 공백으로 구분되어 주어진다.

기약분수는 항상 p/q꼴이며 공백은 주어지지 않는다. p는 분수의 분자이며 q는 분모이다.

모든 테스트 케이스에서 p와 q는 서로소이며, 0 <= p, q <= 2147483647을 만족한다.

출력

각 테스트 케이스마다 첫 줄에 테스트 케이스의 번호와 정답을 공백으로 구분하여 출력한다.

답이 되는 기약분수는 입력 형식과 동일하게 분자/분모 형태로 출력하며, 사이에 공백을 두어선 안 된다.

모든 테스트 케이스에서 답이 되는 분수의 분자와 분모는 32bit 정수 범위를 넘지 않는다.

예제 입력 1

5
1 1/1
2 1/3
3 5/2
4 2178309/1346269
5 1/10000000

예제 출력 1

1 1/2
2 3/2
3 2/5
4 1346269/1860498
5 10000000/9999999
W3sicHJvYmxlbV9pZCI6IjEwNDM2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViYjM0XHVkNTVjIFx1YzcyMFx1YjlhY1x1YzIxOCBcdWQyYjhcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmIzNFx1ZDU1YyBcdWM3MjBcdWI5YWNcdWMyMTggXHVkMmI4XHViOWFjXHViMjk0IFx1YzY0NFx1YzgwNCBcdWM3NzRcdWM5YzQgXHVkMmI4XHViOWFjXHVjNzc0XHViYTcwLCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzgxNVx1Yzc1OFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWI4ZThcdWQyYjhcdWIyOTQgMVwvMVx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+cFwvcVx1Yzc1OCBcdWM2N2NcdWNhYmQgXHVjNzkwXHVjMmRkXHVjNzQwIHBcLyhwK3EpXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5wXC9xXHVjNzU4IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM3OTBcdWMyZGRcdWM3NDAgKHArcSlcL3FcdWM3NzRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVkMmI4XHViOWFjXHVjNzU4IFx1Y2NhYiBcdWMxMzggXHVjZTM1XHVjNzQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVhZDZjXHVjMTMxXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIHNyYz1cIlwvdXNlcnVwbG9hZFwvcG9ydGFibGVhbmdlbFwvMjAxNTA0XC82NGE2MmY1MTdlZWI3MGIxODMwZDhhMTJiNTllMDQ0YS5wbmdcIiBzdHlsZT1cImZvbnQtZmFtaWx5OmFyaWFsLGhlbHZldGljYSx2ZXJkYW5hLHRhaG9tYSxzYW5zLXNlcmlmOyBsaW5lLWhlaWdodDoxLjZlbVwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHViYjM0XHVkNTVjIFx1YzcyMFx1YjlhY1x1YzIxOCBcdWQyYjhcdWI5YWNcdWI5N2MgXHViODA4XHViY2E4IFx1YzYyNFx1YjM1NFx1Yjg1YyhcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWNcdWIyOTQgXHVkNjU0XHVjMGI0XHVkNDVjIFx1YmMyOVx1ZDVhNSkgXHVjMjFjXHVkNjhjXHVkNTU4XHVjNWVjIFx1YzViYlx1YzViNFx1YzljMFx1YjI5NCBcdWMyMThcdWI0ZTRcdWM3NDQgXHViMDk4XHVjNWY0XHVkNTU4XHViYTc0IFx1YzcyMFx1YjlhY1x1YzIxOCBcdWMyMThcdWM1ZjQgRihuKVx1Yzc0NCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiIFx1YmE4NyBcdWFjMWNcdWM3NTggXHVkNTZkXHVjNzQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkYoMSkgPSAxXC8xLCBGKDIpID0gMVwvMiwgRigzKSA9IDJcLzEsIEYoNCkgPSAxXC8zLCBGKDUpID0gM1wvMiwgRig2KSA9IDJcLzMsICZoZWxsaXA7PFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWFlMzBcdWM1N2RcdWJkODRcdWMyMTggcFwvcVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzQgRihuKVx1YzVkMFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjNzIwXHViOWFjXHVjMjE4XHVjNzU4IFx1YjJlNFx1Yzc0YyBcdWMyMThcdWFjMDAgXHViYjM0XHVjNWM3XHVjNzc4XHVjOWMwIFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcblxyXG48cD5cdWM5ODksIEYobik9cFwvcVx1Yzc3YyBcdWI1NGMgRihuKzEpXHVjNzQ0IFx1Y2MzZVx1YzczY1x1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFAgJmxlOyAxMDAwKTxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YzY0MCBcdWFlMzBcdWM1N2RcdWJkODRcdWMyMTggXHVkNTU4XHViMDk4XHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFlMzBcdWM1N2RcdWJkODRcdWMyMThcdWIyOTQgXHVkNTZkXHVjMGMxIHBcL3FcdWFmMzRcdWM3NzRcdWJhNzAgXHVhY2Y1XHViYzMxXHVjNzQwIFx1YzhmY1x1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIHBcdWIyOTQgXHViZDg0XHVjMjE4XHVjNzU4IFx1YmQ4NFx1Yzc5MFx1Yzc3NFx1YmE3MCBxXHViMjk0IFx1YmQ4NFx1YmFhOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDBcdWMxMWMgcFx1YzY0MCBxXHViMjk0IFx1YzExY1x1Yjg1Y1x1YzE4Y1x1Yzc3NFx1YmE3MCwgMCAmbHQ7PSBwLCBxICZsdDs9IDIxNDc0ODM2NDdcdWM3NDQgXHViOWNjXHVjODcxXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWM2NDAgXHVjODE1XHViMmY1XHVjNzQ0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZjVcdWM3NzQgXHViNDE4XHViMjk0IFx1YWUzMFx1YzU3ZFx1YmQ4NFx1YzIxOFx1YjI5NCBcdWM3ODVcdWI4MjUgXHVkNjE1XHVjMmRkXHVhY2ZjIFx1YjNkOVx1Yzc3Y1x1ZDU1OFx1YWM4YyBcdWJkODRcdWM3OTBcL1x1YmQ4NFx1YmFhOCBcdWQ2MTVcdWQwZGNcdWI4NWMgXHVjZDljXHViODI1XHVkNTU4XHViYTcwLCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YjQ1MFx1YzViNFx1YzEyMCBcdWM1NDggXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMFx1YzExYyBcdWIyZjVcdWM3NzQgXHViNDE4XHViMjk0IFx1YmQ4NFx1YzIxOFx1Yzc1OCBcdWJkODRcdWM3OTBcdWM2NDAgXHViZDg0XHViYWE4XHViMjk0IDMyYml0IFx1YzgxNVx1YzIxOCBcdWJjOTRcdWM3MDRcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDQzNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkEgUmF0aW9uYWwgU2VxdWVuY2UiLCJkZXNjcmlwdGlvbiI6IjxwPkFuIGluZmluaXRlIGZ1bGwgYmluYXJ5IHRyZWUgbGFiZWxlZCBieSBwb3NpdGl2ZSByYXRpb25hbCBudW1iZXJzIGlzIGRlZmluZWQgYnk6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VGhlIGxhYmVsIG9mIHRoZSByb290IGlzIDFcLzEuPFwvbGk+XHJcblx0PGxpPlRoZSBsZWZ0IGNoaWxkIG9mIGxhYmVsIHBcL3EgaXMgcFwvKHArcSkuPFwvbGk+XHJcblx0PGxpPlRoZSByaWdodCBjaGlsZCBvZiBsYWJlbCBwXC9xIGlzIChwK3EpXC9xLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZSB0b3Agb2YgdGhlIHRyZWUgaXMgc2hvd24gaW4gdGhlIGZvbGxvd2luZyBmaWd1cmU6PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMzXC9yYXRpb25hbC5wbmdcIiBzdHlsZT1cImhlaWdodDoyODRweDsgd2lkdGg6NTM2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+QSByYXRpb25hbCBzZXF1ZW5jZSBpcyBkZWZpbmVkIGJ5IGRvaW5nIGEgbGV2ZWwgb3JkZXIgKGJyZWFkdGggZmlyc3QpIHRyYXZlcnNhbCBvZiB0aGUgdHJlZSAoaW5kaWNhdGVkIGJ5dGhlIGxpZ2h0IGRhc2hlZCBsaW5lKS4gU28gdGhhdDo8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPkYoMSkgPSAxXC8xLCBGKDIpID0gMVwvMiwgRigzKSA9IDJcLzEsIEYoNCkgPSAxXC8zLCBGKDUpID0gM1wvMiwgRig2KSA9IDJcLzMsICZoZWxsaXA7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB3aGljaCB0YWtlcyBhcyBpbnB1dCBhIHJhdGlvbmFsIG51bWJlciwgcFwvcSwgaW4gbG93ZXN0IHRlcm1zIGFuZCBmaW5kcyB0aGUgbmV4dHJhdGlvbmFsIG51bWJlciBpbiB0aGUgc2VxdWVuY2UuIFRoYXQgaXMsIGlmIEYobikgPSBwXC9xLCB0aGVuIHRoZSByZXN1bHQgaXMgRihuKzEpLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBQLCAoMSAmbGU7IFAgJmxlOyAxMDAwKSwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhIHNldHN0aGF0IGZvbGxvdy4gRWFjaCBkYXRhIHNldCBzaG91bGQgYmUgcHJvY2Vzc2VkIGlkZW50aWNhbGx5IGFuZCBpbmRlcGVuZGVudGx5LjxcL3A+XHJcblxyXG48cD5FYWNoIGRhdGEgc2V0IGNvbnNpc3RzIG9mIGEgc2luZ2xlIGxpbmUgb2YgaW5wdXQuIEl0IGNvbnRhaW5zIHRoZSBkYXRhIHNldCBudW1iZXIsIEssIHdoaWNoIGlzIHRoZW5mb2xsb3dlZCBieSBhIHNwYWNlLCB0aGVuIHRoZSBudW1lcmF0b3Igb2YgdGhlIGZyYWN0aW9uLCBwLCBmb2xsb3dlZCBpbW1lZGlhdGVseSBieSBhIGZvcndhcmQgc2xhc2goXC8pLCBmb2xsb3dlZCBpbW1lZGlhdGVseSBieSB0aGUgZGVub21pbmF0b3Igb2YgdGhlIGZyYWN0aW9uLCBxLiBCb3RoIHAgYW5kIHEgd2lsbCBiZSByZWxhdGl2ZWx5IHByaW1lYW5kIDAgJmx0Oz0gcCwgcSAmbHQ7PSAyMTQ3NDgzNjQ3LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGEgc2V0IHRoZXJlIGlzIGEgc2luZ2xlIGxpbmUgb2Ygb3V0cHV0LiBJdCBjb250YWlucyB0aGUgZGF0YSBzZXQgbnVtYmVyLCBLLCBmb2xsb3dlZCBieSBhc2luZ2xlIHNwYWNlIHdoaWNoIGlzIHRoZW4gZm9sbG93ZWQgYnkgdGhlIG51bWVyYXRvciBvZiB0aGUgZnJhY3Rpb24sIGZvbGxvd2VkIGltbWVkaWF0ZWx5IGJ5IGFmb3J3YXJkIHNsYXNoICgmIzM5O1wvJiMzOTspIGZvbGxvd2VkIGltbWVkaWF0ZWx5IGJ5IHRoZSBkZW5vbWluYXRvciBvZiB0aGUgZnJhY3Rpb24uIElucHV0cyB3aWxsIGJlIGNob3NlbiBzdWNodGhhdCBuZWl0aGVyIHRoZSBudW1lcmF0b3Igbm9yIHRoZSBkZW5vbWluYXRvciB3aWxsIG92ZXJmbG93IGEgMzItYml0IGludGVnZXIuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d