시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHViYWE4XHViNGUwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDBcdWMxMWMgcFx1YzY0MCBxXHViMjk0IFx1YzExY1x1Yjg1Y1x1YzE4Y1x1Yzc3NFx1YmE3MCwgMCAmbGU7IHAsIHEgJmxlOyAyMTQ3NDgzNjQ3XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWNjYWIgXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHViYzg4XHVkNjM4XHVjNjQwIFx1YzgxNVx1YjJmNVx1Yzc0NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmY1XHVjNzc0IFx1YjQxOFx1YjI5NCBcdWFlMzBcdWM1N2RcdWJkODRcdWMyMThcdWIyOTQgXHVjNzg1XHViODI1IFx1ZDYxNVx1YzJkZFx1YWNmYyBcdWIzZDlcdWM3N2NcdWQ1NThcdWFjOGMgXHViZDg0XHVjNzkwXC9cdWJkODRcdWJhYTggXHVkNjE1XHVkMGRjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3MCwgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWI0NTBcdWM1YjRcdWMxMjAgXHVjNTQ4IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDBcdWMxMWMgXHViMmY1XHVjNzc0IFx1YjQxOFx1YjI5NCBcdWJkODRcdWMyMThcdWM3NTggXHViZDg0XHVjNzkwXHVjNjQwIFx1YmQ4NFx1YmFhOFx1YjI5NCAzMmJpdCBcdWM4MTVcdWMyMTggXHViYzk0XHVjNzA0XHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTA0MzYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBIFJhdGlvbmFsIFNlcXVlbmNlIiwiZGVzY3JpcHRpb24iOiI8cD5BbiBpbmZpbml0ZSBmdWxsIGJpbmFyeSB0cmVlIGxhYmVsZWQgYnkgcG9zaXRpdmUgcmF0aW9uYWwgbnVtYmVycyBpcyBkZWZpbmVkIGJ5OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlRoZSBsYWJlbCBvZiB0aGUgcm9vdCBpcyAxXC8xLjxcL2xpPlxyXG5cdDxsaT5UaGUgbGVmdCBjaGlsZCBvZiBsYWJlbCBwXC9xIGlzIHBcLyhwK3EpLjxcL2xpPlxyXG5cdDxsaT5UaGUgcmlnaHQgY2hpbGQgb2YgbGFiZWwgcFwvcSBpcyAocCtxKVwvcS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgdG9wIG9mIHRoZSB0cmVlIGlzIHNob3duIGluIHRoZSBmb2xsb3dpbmcgZmlndXJlOjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzM1wvcmF0aW9uYWwucG5nXCIgc3R5bGU9XCJoZWlnaHQ6Mjg0cHg7IHdpZHRoOjUzNnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkEgcmF0aW9uYWwgc2VxdWVuY2UgaXMgZGVmaW5lZCBieSBkb2luZyBhIGxldmVsIG9yZGVyIChicmVhZHRoIGZpcnN0KSB0cmF2ZXJzYWwgb2YgdGhlIHRyZWUgKGluZGljYXRlZCBieXRoZSBsaWdodCBkYXNoZWQgbGluZSkuIFNvIHRoYXQ6PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj5GKDEpID0gMVwvMSwgRigyKSA9IDFcLzIsIEYoMykgPSAyXC8xLCBGKDQpID0gMVwvMywgRig1KSA9IDNcLzIsIEYoNikgPSAyXC8zLCAmaGVsbGlwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gd2hpY2ggdGFrZXMgYXMgaW5wdXQgYSByYXRpb25hbCBudW1iZXIsIHBcL3EsIGluIGxvd2VzdCB0ZXJtcyBhbmQgZmluZHMgdGhlIG5leHRyYXRpb25hbCBudW1iZXIgaW4gdGhlIHNlcXVlbmNlLiBUaGF0IGlzLCBpZiBGKG4pID0gcFwvcSwgdGhlbiB0aGUgcmVzdWx0IGlzIEYobisxKS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgUCwgKDEgJmxlOyBQICZsZTsgMTAwMCksIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgZGF0YSBzZXRzdGhhdCBmb2xsb3cuIEVhY2ggZGF0YSBzZXQgc2hvdWxkIGJlIHByb2Nlc3NlZCBpZGVudGljYWxseSBhbmQgaW5kZXBlbmRlbnRseS48XC9wPlxyXG5cclxuPHA+RWFjaCBkYXRhIHNldCBjb25zaXN0cyBvZiBhIHNpbmdsZSBsaW5lIG9mIGlucHV0LiBJdCBjb250YWlucyB0aGUgZGF0YSBzZXQgbnVtYmVyLCBLLCB3aGljaCBpcyB0aGVuZm9sbG93ZWQgYnkgYSBzcGFjZSwgdGhlbiB0aGUgbnVtZXJhdG9yIG9mIHRoZSBmcmFjdGlvbiwgcCwgZm9sbG93ZWQgaW1tZWRpYXRlbHkgYnkgYSBmb3J3YXJkIHNsYXNoKFwvKSwgZm9sbG93ZWQgaW1tZWRpYXRlbHkgYnkgdGhlIGRlbm9taW5hdG9yIG9mIHRoZSBmcmFjdGlvbiwgcS4gQm90aCBwIGFuZCBxIHdpbGwgYmUgcmVsYXRpdmVseSBwcmltZWFuZCAwICZsdDs9IHAsIHEgJmx0Oz0gMjE0NzQ4MzY0Ny48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCB0aGVyZSBpcyBhIHNpbmdsZSBsaW5lIG9mIG91dHB1dC4gSXQgY29udGFpbnMgdGhlIGRhdGEgc2V0IG51bWJlciwgSywgZm9sbG93ZWQgYnkgYXNpbmdsZSBzcGFjZSB3aGljaCBpcyB0aGVuIGZvbGxvd2VkIGJ5IHRoZSBudW1lcmF0b3Igb2YgdGhlIGZyYWN0aW9uLCBmb2xsb3dlZCBpbW1lZGlhdGVseSBieSBhZm9yd2FyZCBzbGFzaCAoJiMzOTtcLyYjMzk7KSBmb2xsb3dlZCBpbW1lZGlhdGVseSBieSB0aGUgZGVub21pbmF0b3Igb2YgdGhlIGZyYWN0aW9uLiBJbnB1dHMgd2lsbCBiZSBjaG9zZW4gc3VjaHRoYXQgbmVpdGhlciB0aGUgbnVtZXJhdG9yIG5vciB0aGUgZGVub21pbmF0b3Igd2lsbCBvdmVyZmxvdyBhIDMyLWJpdCBpbnRlZ2VyLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==