시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 27 9 5 29.412%

문제

유리수는 두 정수의 비로 나타낼 수 있다. 분자(n)와 분모(d)가 주어지면 이 분수를 n/d으로 쓴다. 유리수의 표현 방법은 유일하지 않다. 예를 들어, 1/2과 2/4는 그 값이 같다. 어떤 유리수 표현법 n/d이 gcd(|n|, |d|) = 1이라면 이것이 "기약분수로 표현되었다"라고 한다. 따라서 1/2은 기약분수로 표현되었지만 2/4는 아니다.

유리수의 덧셈은 다음과 같이 정의된다. 오른쪽 항이 기약분수로 표현될 필요는 없다는 점에 주목하라.

\[\frac{n_1}{d_1} + \frac{n_2}{d_2} = \frac{n_1d_2 + n_2d_1}{d_1d_2}\]

분자가 분모보다 크거나 같은 유리수는 대분수 꼴로 표현할 수 있는데, 이것은 정수부와 소수부로 이루어 진다. 예를 들어, $5 {{1}\over{3}}$은 16/3과 같은 값을 가지는 대분수 표현이다.

당신이 할 일은 유리수열을 읽어 그 합을 출력하는 것이다.

입력

입력은 몇 개의 테스트로 구성된다. 각 테스트의 정보는 첫 줄에 n(1 ≤ n < 1000)을 포함한다. n = 0인 경우 입력이 끝난다.

다음 n개의 줄은 공백이 없는 하나의 문자열이다. 각 문자열은 유리수 하나를 나타내며, 다음 세 형태 중 하나이고 기약분수로 표현되지 않을 수 있다 (w, n과 d는 정수이다: 0 ≤ w,n < 1000, 1 ≤ d < 1000).

  • w,n/d: (w * d + n) / d와 값이 같은 대분수
  • n/d: 정수부가 0인 유리수
  • w: 소수부가 0인 정수

출력

출력은 화면에 나온 대로 테스트 번호를 포함하여 합을 출력한다. 만약 합의 정수부나 소수부가 없다면 각 부분을 생략하여 출력한다. 특수한 경우로, 정수부와 소수부가 모두 없다면 0을 출력해야 한다.

예제 입력 1

2
1/2
1/3
3
1/3
2/6
3/9
3
1
2/3
4,5/6
0

예제 출력 1

Test 1: 5/6
Test 2: 1
Test 3: 6,1/2

힌트

W3sicHJvYmxlbV9pZCI6IjkyMTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyZTBcdWIwOThcdWIyOTQgXHViZDg0XHVjMjE4IFx1YWNjNFx1YzBiMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNzIwXHViOWFjXHVjMjE4XHViMjk0IFx1YjQ1MCBcdWM4MTVcdWMyMThcdWM3NTggXHViZTQ0XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWJkODRcdWM3OTAobilcdWM2NDAmbmJzcDtcdWJkODRcdWJhYTgoZClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTc0IFx1Yzc3NCBcdWJkODRcdWMyMThcdWI5N2MgblwvZFx1YzczY1x1Yjg1YyBcdWM0ZjRcdWIyZTQuIFx1YzcyMFx1YjlhY1x1YzIxOFx1Yzc1OCBcdWQ0NWNcdWQ2MDQgXHViYzI5XHViYzk1XHVjNzQwIFx1YzcyMFx1Yzc3Y1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIDFcLzJcdWFjZmMmbmJzcDsyXC80XHViMjk0IFx1YWRmOCBcdWFjMTJcdWM3NzQgXHVhYzE5XHViMmU0LiBcdWM1YjRcdWI1YTQgXHVjNzIwXHViOWFjXHVjMjE4IFx1ZDQ1Y1x1ZDYwNFx1YmM5NSBuXC9kXHVjNzc0IGdjZCh8bnwsIHxkfCkgPSAxXHVjNzc0XHViNzdjXHViYTc0IFx1Yzc3NFx1YWM4M1x1Yzc3NCAmcXVvdDtcdWFlMzBcdWM1N2RcdWJkODRcdWMyMThcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDE4XHVjNWM4XHViMmU0JnF1b3Q7XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIDFcLzJcdWM3NDAmbmJzcDtcdWFlMzBcdWM1N2RcdWJkODRcdWMyMThcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDE4XHVjNWM4XHVjOWMwXHViOWNjIDJcLzRcdWIyOTQgXHVjNTQ0XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3MjBcdWI5YWNcdWMyMThcdWM3NTggXHViMzY3XHVjMTQ4XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjODE1XHVjNzU4XHViNDFjXHViMmU0LiBcdWM2MjRcdWI5NzhcdWNhYmQgXHVkNTZkXHVjNzc0IFx1YWUzMFx1YzU3ZFx1YmQ4NFx1YzIxOFx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MjAgXHVkNTQ0XHVjNjk0XHViMjk0IFx1YzVjNlx1YjJlNFx1YjI5NCBcdWM4MTBcdWM1ZDAgXHVjOGZjXHViYWE5XHVkNTU4XHViNzdjLjxcL3A+XHJcblxyXG48cD5cXFtcXGZyYWN7bl8xfXtkXzF9ICsgXFxmcmFje25fMn17ZF8yfSA9IFxcZnJhY3tuXzFkXzIgKyBuXzJkXzF9e2RfMWRfMn1cXF08XC9wPlxyXG5cclxuPHA+XHViZDg0XHVjNzkwXHVhYzAwIFx1YmQ4NFx1YmFhOFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzcyMFx1YjlhY1x1YzIxOFx1YjI5NCBcdWIzMDBcdWJkODRcdWMyMTggXHVhZjM0XHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHViMzcwLCBcdWM3NzRcdWFjODNcdWM3NDAgXHVjODE1XHVjMjE4XHViZDgwXHVjNjQwIFx1YzE4Y1x1YzIxOFx1YmQ4MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjQgXHVjOWM0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAkNSB7ezF9XFxvdmVyezN9fSRcdWM3NDAmbmJzcDsxNlwvM1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhYzEyXHVjNzQ0IFx1YWMwMFx1YzljMFx1YjI5NCBcdWIzMDBcdWJkODRcdWMyMTggXHVkNDVjXHVkNjA0XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZjlcdWMyZTBcdWM3NzQgXHVkNTYwIFx1Yzc3Y1x1Yzc0MCBcdWM3MjBcdWI5YWNcdWMyMThcdWM1ZjRcdWM3NDQgXHVjNzdkXHVjNWI0IFx1YWRmOCBcdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWJhODcgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MWNcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjhcdWM3NTggXHVjODE1XHViY2Y0XHViMjk0IFx1Y2NhYiBcdWM5MDRcdWM1ZDAmbmJzcDtuKDEgJmxlOyBuJm5ic3A7Jmx0OyAxMDAwKVx1Yzc0NCBcdWQzZWNcdWQ1NjhcdWQ1NWNcdWIyZTQuIG4gPSAwXHVjNzc4IFx1YWNiZFx1YzZiMCBcdWM3ODVcdWI4MjVcdWM3NzQgXHViMDVkXHViMDljXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NDAgXHVhY2Y1XHViYzMxXHVjNzc0IFx1YzVjNlx1YjI5NCBcdWQ1NThcdWIwOThcdWM3NTggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LiBcdWFjMDEgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YzcyMFx1YjlhY1x1YzIxOCBcdWQ1NThcdWIwOThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViYTcwLCBcdWIyZTRcdWM3NGMgXHVjMTM4IFx1ZDYxNVx1ZDBkYyBcdWM5MTEgXHVkNTU4XHViMDk4XHVjNzc0XHVhY2UwIFx1YWUzMFx1YzU3ZFx1YmQ4NFx1YzIxOFx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MThcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQgKHcsIG5cdWFjZmMgZFx1YjI5NCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQ6IDAgJmxlOyB3LG4gJmx0OyAxMDAwLCAxICZsZTsgZCAmbHQ7IDEwMDApLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPncsblwvZDogKHcgKiBkICsmbmJzcDtuKSBcLyBkXHVjNjQwIFx1YWMxMlx1Yzc3NCBcdWFjMTlcdWM3NDAgXHViMzAwXHViZDg0XHVjMjE4PFwvbGk+XHJcblx0PGxpPm5cL2Q6IFx1YzgxNVx1YzIxOFx1YmQ4MFx1YWMwMCAwXHVjNzc4IFx1YzcyMFx1YjlhY1x1YzIxODxcL2xpPlxyXG5cdDxsaT53OiBcdWMxOGNcdWMyMThcdWJkODBcdWFjMDAgMFx1Yzc3OCBcdWM4MTVcdWMyMTg8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2Q5Y1x1YjgyNVx1Yzc0MCBcdWQ2NTRcdWJhNzRcdWM1ZDAgXHViMDk4XHVjNjI4IFx1YjMwMFx1Yjg1YyBcdWQxNGNcdWMyYTRcdWQyYjggXHViYzg4XHVkNjM4XHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YzVlYyBcdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVkNTY5XHVjNzU4IFx1YzgxNVx1YzIxOFx1YmQ4MFx1YjA5OCBcdWMxOGNcdWMyMThcdWJkODBcdWFjMDAgXHVjNWM2XHViMmU0XHViYTc0IFx1YWMwMSBcdWJkODBcdWJkODRcdWM3NDQgXHVjMGRkXHViN2I1XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVkMmI5XHVjMjE4XHVkNTVjIFx1YWNiZFx1YzZiMFx1Yjg1YywgXHVjODE1XHVjMjE4XHViZDgwXHVjNjQwIFx1YzE4Y1x1YzIxOFx1YmQ4MFx1YWMwMCBcdWJhYThcdWI0NTAgXHVjNWM2XHViMmU0XHViYTc0IDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5MjE1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRnVuIFdpdGggRnJhY3Rpb25zIiwiZGVzY3JpcHRpb24iOiI8cD5BIHJhdGlvbmFsIG51bWJlciBjYW4gYmUgcmVwcmVzZW50ZWQgYXMgdGhlIHJhdGlvIG9mIHR3byBpbnRlZ2VycywgcmVmZXJyZWQgdG8gYXMgdGhlIG51bWVyYXRvciAobikgYW5kIHRoZSBkZW5vbWluYXRvciAoZCkgYW5kIHdyaXR0ZW4gblwvZC4gQSByYXRpb25hbCBudW1iZXImIzM5O3MgcmVwcmVzZW50YXRpb24gaXMgbm90IHVuaXF1ZS4gRm9yIGV4YW1wbGUgdGhlIHJhdGlvbmFsIG51bWJlcnMgMVwvMiBhbmQgMlwvNCBhcmUgZXF1aXZhbGVudC4gQSByYXRpb25hbCBudW1iZXIgcmVwcmVzZW50YXRpb24gaXMgZGVzY3JpYmVkIGFzICZxdW90O2luIGxvd2VzdCB0ZXJtcyZxdW90OyBpZiB0aGUgbnVtZXJhdG9yIGFuZCBkZW5vbWluYXRvciBoYXZlIG5vIGNvbW1vbiBmYWN0b3JzLiBUaHVzIDFcLzIgaXMgaW4gbG93ZXN0IHRlcm1zIGJ1dCAyXC80IGlzIG5vdC4gQSByYXRpb25hbCBudW1iZXIgY2FuIGJlIHJlZHVjZWQgdG8gbG93ZXN0IHRlcm1zIGJ5IGRpdmlkaW5nIGJ5IHRoZSBncmVhdGVzdCBjb21tb24gZGl2aXNvciBvZiBuIGFuZCBkLjxcL3A+XHJcblxyXG48cD5BZGRpdGlvbiBvZiByYXRpb25hbCBudW1iZXJzIGlzIGRlZmluZWQgYXMgZm9sbG93cy4gTm90ZSB0aGF0IHRoZSByaWdodCBoYW5kIHNpZGUgb2YgdGhpcyBlcXVhbGl0eSB3aWxsIG5vdCBuZWNlc3NhcmlseSBiZSBpbiBsb3dlc3QgdGVybXMuPFwvcD5cclxuXHJcbjxwPlxcW1xcZnJhY3tuXzF9e2RfMX0gKyBcXGZyYWN7bl8yfXtkXzJ9ID0gXFxmcmFje25fMWRfMiArIG5fMmRfMX17ZF8xZF8yfVxcXTxcL3A+XHJcblxyXG48cD5BIHJhdGlvbmFsIG51bWJlciBmb3Igd2hpY2ggdGhlIG51bWVyYXRvciBpcyBncmVhdGVyIHRoYW4gb3IgZXF1YWwgdG8gdGhlIGRlbm9taW5hdG9yIGNhbiBiZSBkaXNwbGF5ZWQgaW4gbWl4ZWQgZm9ybWF0LCB3aGljaCBpbmNsdWRlcyBhIHdob2xlIG51bWJlciBwYXJ0IGFuZCBhIGZyYWN0aW9uYWwgcGFydC4gRm9yIGV4YW1wbGUsICQ1IHt7MX1cXG92ZXJ7M319JCBpcyBhIG1peGVkIGZvcm1hdCByZXByZXNlbnRhdGlvbiBvZiB0aGUgcmF0aW9uYWwgbnVtYmVyIDE2XC8zLjxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQgcmVhZHMgYSBzZXF1ZW5jZSBvZiByYXRpb25hbCBudW1iZXJzIGFuZCBkaXNwbGF5cyB0aGVpciBzdW0uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCB3aWxsIGNvbnNpc3Qgb2Ygc3BlY2lmaWNhdGlvbnMgZm9yIGEgc2VyaWVzIG9mIHRlc3RzLiBJbmZvcm1hdGlvbiBmb3IgZWFjaCB0ZXN0IGJlZ2lucyB3aXRoIGEgbGluZSBjb250YWluaW5nIGEgc2luZ2xlIGludGVnZXIgMSAmbHQ7PSBuICZsdDsgMTAwMCBpbmRpY2F0aW5nIGhvdyBtYW55IHZhbHVlcyBmb2xsb3cuIEEgY291bnQgb2YgemVybyB0ZXJtaW5hdGVzIHRoZSBpbnB1dC48XC9wPlxyXG5cclxuPHA+VGhlIG4gZm9sbG93aW5nIGxpbmVzIGVhY2ggY29udGFpbiBhIHNpbmdsZSBzdHJpbmcgd2l0aCBubyBlbWJlZGRlZCB3aGl0ZXNwYWNlIC4gRWFjaCBzdHJpbmcgcmVwcmVzZW50cyBhIHJhdGlvbmFsIG51bWJlciwgd2hpY2ggY291bGQgYmUgaW4gYW55IG9mIHRoZSBmb2xsb3dpbmcgZm9ybXMgYW5kIHdpbGwgbm90IG5lY2Vzc2FyaWx5IGJlIGluIGxvd2VzdCB0ZXJtcyAodywgbiwgYW5kIGQgYXJlIGludGVnZXJzOiAwICZsdDs9IHcsbiAmbHQ7IDEwMDAsIDEgJmx0Oz0gZCAmbHQ7IDEwMDApLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPncsblwvZDogYSBtaXhlZCBudW1iZXIgZXF1aXZhbGVudCB0byB0aGUgcmF0aW9uYWwgbnVtYmVyICh3KmQgKyBuKSBcLyBkLjxcL2xpPlxyXG5cdDxsaT5uXC9kOiBhIHJhdGlvbmFsIG51bWJlciB3aXRoIGEgemVybyB3aG9sZSBudW1iZXIgcGFydDxcL2xpPlxyXG5cdDxsaT53OiBhIHdob2xlIG51bWJlciB3aXRoIGEgemVybyBmcmFjdGlvbmFsIHBhcnQ8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBzaG91bGQgY29uc2lzdCBvZiBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNvbXByaXNpbmcgdGhlIHRlc3QgbnVtYmVyIChmb3JtYXR0ZWQgYXMgc2hvd24pIGZvbGxvd2VkIGJ5IGEgc2luZ2xlIHNwYWNlIGFuZCB0aGUgc3VtIG9mIHRoZSBpbnB1dCBudW1iZXIgc2VxdWVuY2UuIFRoZSBzdW0gc2hvdWxkIGJlIGRpc3BsYXllZCBpbiBsb3dlc3QgdGVybXMgdXNpbmcgbWl4ZWQgbnVtYmVyIGZvcm1hdC4gSWYgZWl0aGVyIHRoZSB3aG9sZSBudW1iZXIgcGFydCBvciB0aGUgZnJhY3Rpb25hbCBwYXJ0IGlzIHplcm8sIHRoYXQgcGFydCBzaG91bGQgYmUgb21pdHRlZC4gQXMgYSBzcGVjaWFsIGNhc2UsIGlmIGJvdGggcGFydHMgYXJlIHplcm8sIHRoZSB2YWx1ZSBzaG91bGQgYmUgZGlzcGxheWVkIGFzIGEgc2luZ2xlIDAuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d