시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB68911987155030.524%

문제

이제 10 살이 된 헨리(Henry)는 수학에 소질이 있다. 수학선생님인 아메스(Ahmes)는 오늘 헨리에게 분수에 대해 가르쳐줬고, 헨리는 분수를 이리저리 계산해보는 것이 너무 재미있었다. 그러던 중에 헨리는 1 보다 작은 분수를 여러 개의 서로 다른 단위분수의 합으로 표현할 수 있다는 것을 알아내었다. 여기서 단위분수란 분자가 1 인 분수를 말한다. 헨리는 여러 개의 분수에 대해 이를 시도해봤고, 시도해본 분수들은 모두 서로 다른 단위분수의 합으로 표현할 수 있었다. 예를 들어, \(\frac{4}{23}\)은 \(\frac{1}{6} + \frac{1}{138}\)와 같이 두 개의 단위 분수의 합으로 나타낼 수 있다. 

헨리는 이런 발견을 선생님인 아메스에게 자랑스럽게 이야기했다. 아메스는 이를 듣고는 크게 기뻐하며 어린 제자를 칭찬했고, 이와 같이 하나의 분수를 서로 다른 단위분수의 합으로 표현한 것을 헨리식 표현법(Henry representation)이라고 이름 지었다. 즉, 분수 \(\frac{a}{b}\)의 헨리식 표현법은 총합이 \(\frac{a}{b}\) 와 같게 되는 서로 다른 단위분수의 나열이다. 헨리와 아메스는 헨리식 표현법에 대하여 더욱 연구하였고, 마침내 모든 1 보다 작은 분수는 헨리식 표현법이 가능함을 증명하였다. 또한 헨리식 표현법이 유일하지 않다는 것도 알 수 있었다. 예를 들면, \(\frac{5}{7} = \frac{1}{2} + \frac{1}{5} + \frac{1}{70} = \frac{1}{2}+\frac{1}{6} + \frac{1}{21} = \frac{1}{2} + \frac{1}{7} + \frac{1}{14}\) 와 같이 여러 가지 다른 헨리식 표현법이 존재할 수 있다. 단, 정의에 의해, 헨리식 표현법에는 같은 단위분수가 두 개 이상 포함될 수 없으므로 \(\frac{2}{3} = \frac{1}{3} + \frac{1}{3}\) 는 헨리식 표현법이 아님을 유념해야 한다.

아메스와 헨리는 또한 주어진 분수의 헨리식 표현법을 구하는 간단한 방법도 고안해냈다. \(a < b\) 인 양의 정수 \(a\)와 \(b\)로 이루어진 분수 \(\frac{a}{b}\)가 주어질 때에, 먼저 \(\frac{1}{x_1} \le \frac{a}{b}\)를 만족하는 가장 큰 단위 분수 \(\frac{1}{x_1}\)를 계산한다. 그런 다음 \(\frac{a}{b}\) 에서 \(\frac{1}{x_1}\)를 뺀 나머지에 대하여 위의 과정을 반복한다. 즉, \(\frac{1}{x_2} \le \frac{a}{b} - \frac{1}{x_1}\)를 만족하는 가장 큰 단위분수 \(\frac{1}{x_2}\)를 계산하고 뺀다. 이러한 과정을 나머지가 남지 않을 때까지 반복한다. 그러면 서로 다른 단위분수들 \(\frac{1}{x_1}, \frac{1}{x_2}, \frac{1}{x_3}, \dots\)을 순서대로 얻게 되며 그들의 합은 정확히 \(\frac{a}{b}\)와 같아진다. 아메스와 헨리는 이 알고리즘이 항상 종료하며 합이 \(\frac{a}{b}\)가 되는 서로 다른 단위분수들, 즉 헨리식 표현법을 출력함을 증명하였다.

아메스와 헨리는 당신에게 그들의 알고리즘을 컴퓨터 프로그램으로 구현해줄 것을 부탁했다. 입력으로 주어지는 1 보다 작은 분수 \(\frac{a}{b}\) 를 아메스와 헨리의 알고리즘을 수행하여 헨리식 표현법을 계산할 때에 마지막 단위 분수의 분모를 출력하는 프로그램을 작성하시오. 예를 들어. \(\frac{a}{b} = \frac{5}{7}\)라면, 아메스와 헨리의 알고리즘은 \(\frac{5}{7} = \frac{1}{2} + \frac{1}{5} + \frac{1}{70}\) 을 출력하게 되므로 당신의 프로그램은 반드시 70 을 출력해야 한다.

입력

입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 개수 T 가 정수로 주어진다. 각 테스트 데이터는 한 줄로 구성되며, 여기에는 입력 분수 \(\frac{a}{b}\)를 의미하는 두 개의 정수 \(a\)와 \(b\) (1 ≤ \(a\) < \(b\) ≤ 10,000) 가 주어진다. 이때, \(a\)와 \(b\)는 서로소이며, 입력분수 \(\frac{a}{b}\) 에 대해 아메스와 헨리의 알고리즘을 실행했을 때에 출력되는 단위 분수가 순서대로 \(\frac{1}{x_1},\frac{1}{x_2},\frac{1}{x_3},\cdots,\frac{1}{x_m}\) 라면, \(bx_1x_2 \cdots x_{m-1} < 2^{31}\) 의 부등식을 만족한다고 가정할 수 있다.

출력

출력은 표준출력을 사용한다. 각 테스트 데이터에 대해, 정확히 한 줄을 출력해야 하며 여기에는 정수 하나만을 출력한다. 이 정수는 아메스와 헨리의 알고리즘을 입력 분수 \(\frac{a}{b}\) 에 대해 실행했을 때, 출력되는 헨리식 표현법의 마지막 단위분수의 분모와 같아야 한다. 

예제 입력 1

3
4 23
5 7
8 11

예제 출력 1

138
70
4070
W3sicHJvYmxlbV9pZCI6IjEwMjUzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNWU4XHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3NzRcdWM4MWMgMTAgXHVjMGI0XHVjNzc0IFx1YjQxYyBcdWQ1ZThcdWI5YWMoSGVucnkpXHViMjk0IFx1YzIxOFx1ZDU1OVx1YzVkMCBcdWMxOGNcdWM5YzhcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWMyMThcdWQ1NTlcdWMxMjBcdWMwZGRcdWIyZDhcdWM3NzggXHVjNTQ0XHViYTU0XHVjMmE0KEFobWVzKVx1YjI5NCBcdWM2MjRcdWIyOTggXHVkNWU4XHViOWFjXHVjNWQwXHVhYzhjIFx1YmQ4NFx1YzIxOFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVhYzAwXHViOTc0XHVjY2QwXHVjOTJjXHVhY2UwLCBcdWQ1ZThcdWI5YWNcdWIyOTQgXHViZDg0XHVjMjE4XHViOTdjIFx1Yzc3NFx1YjlhY1x1YzgwMFx1YjlhYyBcdWFjYzRcdWMwYjBcdWQ1NzRcdWJjZjRcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YjEwOFx1YmIzNCBcdWM3YWNcdWJiZjhcdWM3ODhcdWM1YzhcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YjM1OCBcdWM5MTFcdWM1ZDAgXHVkNWU4XHViOWFjXHViMjk0IDEgXHViY2Y0XHViMmU0IFx1Yzc5MVx1Yzc0MCBcdWJkODRcdWMyMThcdWI5N2MgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjJlOFx1YzcwNFx1YmQ4NFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YzU0Y1x1YzU0NFx1YjBiNFx1YzVjOFx1YjJlNC4gXHVjNWVjXHVhZTMwXHVjMTFjIFx1YjJlOFx1YzcwNFx1YmQ4NFx1YzIxOFx1Yjc4MCBcdWJkODRcdWM3OTBcdWFjMDAgMSBcdWM3NzggXHViZDg0XHVjMjE4XHViOTdjIFx1YjlkMFx1ZDU1Y1x1YjJlNC4gXHVkNWU4XHViOWFjXHViMjk0IFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHViZDg0XHVjMjE4XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWM3NzRcdWI5N2MgXHVjMmRjXHViM2M0XHVkNTc0XHViZDI0XHVhY2UwLCBcdWMyZGNcdWIzYzRcdWQ1NzRcdWJjZjggXHViZDg0XHVjMjE4XHViNGU0XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjJlOFx1YzcwNFx1YmQ4NFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM1YzhcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFxcKFxcZnJhY3s0fXsyM31cXClcdWM3NDAgXFwoXFxmcmFjezF9ezZ9ICsgXFxmcmFjezF9ezEzOH1cXClcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHViMmU4XHVjNzA0IFx1YmQ4NFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1ZDVlOFx1YjlhY1x1YjI5NCBcdWM3NzRcdWI3ZjAgXHViYzFjXHVhY2FjXHVjNzQ0IFx1YzEyMFx1YzBkZFx1YjJkOFx1Yzc3OCBcdWM1NDRcdWJhNTRcdWMyYTRcdWM1ZDBcdWFjOGMgXHVjNzkwXHViNzkxXHVjMmE0XHViN2ZkXHVhYzhjIFx1Yzc3NFx1YzU3Y1x1YWUzMFx1ZDU4OFx1YjJlNC4gXHVjNTQ0XHViYTU0XHVjMmE0XHViMjk0IFx1Yzc3NFx1Yjk3YyBcdWI0ZTNcdWFjZTBcdWIyOTQgXHVkMDZjXHVhYzhjIFx1YWUzMFx1YmVkMFx1ZDU1OFx1YmE3MCBcdWM1YjRcdWI5YjAgXHVjODFjXHVjNzkwXHViOTdjIFx1Y2U2ZFx1Y2MyY1x1ZDU4OFx1YWNlMCwgXHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWQ1NThcdWIwOThcdWM3NTggXHViZDg0XHVjMjE4XHViOTdjIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViMmU4XHVjNzA0XHViZDg0XHVjMjE4XHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NWMgXHVhYzgzXHVjNzQ0IFx1ZDVlOFx1YjlhY1x1YzJkZCBcdWQ0NWNcdWQ2MDRcdWJjOTUoSGVucnkgcmVwcmVzZW50YXRpb24pXHVjNzc0XHViNzdjXHVhY2UwIFx1Yzc3NFx1Yjk4NCBcdWM5YzBcdWM1YzhcdWIyZTQuIFx1Yzk4OSwgXHViZDg0XHVjMjE4IFxcKFxcZnJhY3thfXtifVxcKVx1Yzc1OCBcdWQ1ZThcdWI5YWNcdWMyZGQgXHVkNDVjXHVkNjA0XHViYzk1XHVjNzQwIFx1Y2QxZFx1ZDU2OVx1Yzc3NCBcXChcXGZyYWN7YX17Yn1cXCkgXHVjNjQwIFx1YWMxOVx1YWM4YyBcdWI0MThcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWIyZThcdWM3MDRcdWJkODRcdWMyMThcdWM3NTggXHViMDk4XHVjNWY0XHVjNzc0XHViMmU0LiBcdWQ1ZThcdWI5YWNcdWM2NDAgXHVjNTQ0XHViYTU0XHVjMmE0XHViMjk0IFx1ZDVlOFx1YjlhY1x1YzJkZCBcdWQ0NWNcdWQ2MDRcdWJjOTVcdWM1ZDAgXHViMzAwXHVkNTU4XHVjNWVjIFx1YjM1NFx1YzZiMSBcdWM1ZjBcdWFkNmNcdWQ1NThcdWM2MDBcdWFjZTAsIFx1YjljOFx1Y2U2OFx1YjBiNCBcdWJhYThcdWI0ZTAgMSBcdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIFx1YmQ4NFx1YzIxOFx1YjI5NCBcdWQ1ZThcdWI5YWNcdWMyZGQgXHVkNDVjXHVkNjA0XHViYzk1XHVjNzc0IFx1YWMwMFx1YjJhNVx1ZDU2OFx1Yzc0NCBcdWM5OWRcdWJhODVcdWQ1NThcdWM2MDBcdWIyZTQuIFx1YjYxMFx1ZDU1YyBcdWQ1ZThcdWI5YWNcdWMyZGQgXHVkNDVjXHVkNjA0XHViYzk1XHVjNzc0IFx1YzcyMFx1Yzc3Y1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyZTRcdWIyOTQgXHVhYzgzXHViM2M0IFx1YzU0YyBcdWMyMTggXHVjNzg4XHVjNWM4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHViYTc0LCBcXChcXGZyYWN7NX17N30gPSBcXGZyYWN7MX17Mn0gKyBcXGZyYWN7MX17NX0gKyBcXGZyYWN7MX17NzB9ID0gXFxmcmFjezF9ezJ9K1xcZnJhY3sxfXs2fSArIFxcZnJhY3sxfXsyMX0gPSBcXGZyYWN7MX17Mn0gKyBcXGZyYWN7MX17N30gKyBcXGZyYWN7MX17MTR9XFwpIFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMCBcdWIyZTRcdWI5NzggXHVkNWU4XHViOWFjXHVjMmRkIFx1ZDQ1Y1x1ZDYwNFx1YmM5NVx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViMmU4LCBcdWM4MTVcdWM3NThcdWM1ZDAgXHVjNzU4XHVkNTc0LCBcdWQ1ZThcdWI5YWNcdWMyZGQgXHVkNDVjXHVkNjA0XHViYzk1XHVjNWQwXHViMjk0IFx1YWMxOVx1Yzc0MCBcdWIyZThcdWM3MDRcdWJkODRcdWMyMThcdWFjMDAgXHViNDUwIFx1YWMxYyBcdWM3NzRcdWMwYzEgXHVkM2VjXHVkNTY4XHViNDIwIFx1YzIxOCBcdWM1YzZcdWM3M2NcdWJiYzBcdWI4NWMgXFwoXFxmcmFjezJ9ezN9ID0gXFxmcmFjezF9ezN9ICsgXFxmcmFjezF9ezN9XFwpIFx1YjI5NCBcdWQ1ZThcdWI5YWNcdWMyZGQgXHVkNDVjXHVkNjA0XHViYzk1XHVjNzc0IFx1YzU0NFx1YjJkOFx1Yzc0NCBcdWM3MjBcdWIxNTBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWJhNTRcdWMyYTRcdWM2NDAgXHVkNWU4XHViOWFjXHViMjk0IFx1YjYxMFx1ZDU1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViZDg0XHVjMjE4XHVjNzU4IFx1ZDVlOFx1YjlhY1x1YzJkZCBcdWQ0NWNcdWQ2MDRcdWJjOTVcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1YWMwNFx1YjJlOFx1ZDU1YyBcdWJjMjlcdWJjOTVcdWIzYzQgXHVhY2UwXHVjNTQ4XHVkNTc0XHViMGM4XHViMmU0LiBcXChhICZsdDsgYlxcKSBcdWM3NzggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBcXChhXFwpXHVjNjQwIFxcKGJcXClcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmQ4NFx1YzIxOCBcXChcXGZyYWN7YX17Yn1cXClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0Y1x1YzVkMCwgXHViYTNjXHVjODAwIFxcKFxcZnJhY3sxfXt4XzF9IFxcbGUgXFxmcmFje2F9e2J9XFwpXHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YjJlOFx1YzcwNCBcdWJkODRcdWMyMTggXFwoXFxmcmFjezF9e3hfMX1cXClcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3ZjAgXHViMmU0XHVjNzRjIFxcKFxcZnJhY3thfXtifVxcKSBcdWM1ZDBcdWMxMWMgXFwoXFxmcmFjezF9e3hfMX1cXClcdWI5N2MgXHViZTgwIFx1YjA5OFx1YmEzOFx1YzljMFx1YzVkMCBcdWIzMDBcdWQ1NThcdWM1ZWMgXHVjNzA0XHVjNzU4IFx1YWNmY1x1YzgxNVx1Yzc0NCBcdWJjMThcdWJjZjVcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgXFwoXFxmcmFjezF9e3hfMn0gXFxsZSBcXGZyYWN7YX17Yn0gLSBcXGZyYWN7MX17eF8xfVxcKVx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWIyZThcdWM3MDRcdWJkODRcdWMyMTggXFwoXFxmcmFjezF9e3hfMn1cXClcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTU4XHVhY2UwIFx1YmU4MFx1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YWNmY1x1YzgxNVx1Yzc0NCBcdWIwOThcdWJhMzhcdWM5YzBcdWFjMDAgXHViMGE4XHVjOWMwIFx1YzU0YVx1Yzc0NCBcdWI1NGNcdWFlNGNcdWM5YzAgXHViYzE4XHViY2Y1XHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3ZWNcdWJhNzQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWIyZThcdWM3MDRcdWJkODRcdWMyMThcdWI0ZTQgXFwoXFxmcmFjezF9e3hfMX0sIFxcZnJhY3sxfXt4XzJ9LCBcXGZyYWN7MX17eF8zfSwgXFxkb3RzXFwpXHVjNzQ0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM1YmJcdWFjOGMgXHViNDE4XHViYTcwIFx1YWRmOFx1YjRlNFx1Yzc1OCBcdWQ1NjlcdWM3NDAgXHVjODE1XHVkNjU1XHVkNzg4IFxcKFxcZnJhY3thfXtifVxcKVx1YzY0MCBcdWFjMTlcdWM1NDRcdWM5YzRcdWIyZTQuIFx1YzU0NFx1YmE1NFx1YzJhNFx1YzY0MCBcdWQ1ZThcdWI5YWNcdWIyOTQgXHVjNzc0IFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1Yzc3NCBcdWQ1NmRcdWMwYzEgXHVjODg1XHViOGNjXHVkNTU4XHViYTcwIFx1ZDU2OVx1Yzc3NCBcXChcXGZyYWN7YX17Yn1cXClcdWFjMDAgXHViNDE4XHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViMmU4XHVjNzA0XHViZDg0XHVjMjE4XHViNGU0LCBcdWM5ODkgXHVkNWU4XHViOWFjXHVjMmRkIFx1ZDQ1Y1x1ZDYwNFx1YmM5NVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NjhcdWM3NDQgXHVjOTlkXHViYTg1XHVkNTU4XHVjNjAwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWJhNTRcdWMyYTRcdWM2NDAgXHVkNWU4XHViOWFjXHViMjk0IFx1YjJmOVx1YzJlMFx1YzVkMFx1YWM4YyBcdWFkZjhcdWI0ZTRcdWM3NTggXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQ0IFx1Y2VmNFx1ZDRlOFx1ZDEzMCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3M2NcdWI4NWMgXHVhZDZjXHVkNjA0XHVkNTc0XHVjOTA0IFx1YWM4M1x1Yzc0NCBcdWJkODBcdWQwYzFcdWQ1ODhcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgMSBcdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIFx1YmQ4NFx1YzIxOCBcXChcXGZyYWN7YX17Yn1cXCkgXHViOTdjIFx1YzU0NFx1YmE1NFx1YzJhNFx1YzY0MCBcdWQ1ZThcdWI5YWNcdWM3NTggXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQ0IFx1YzIxOFx1ZDU4OVx1ZDU1OFx1YzVlYyBcdWQ1ZThcdWI5YWNcdWMyZGQgXHVkNDVjXHVkNjA0XHViYzk1XHVjNzQ0IFx1YWNjNFx1YzBiMFx1ZDU2MCBcdWI1NGNcdWM1ZDAgXHViOWM4XHVjOWMwXHViOWM5IFx1YjJlOFx1YzcwNCBcdWJkODRcdWMyMThcdWM3NTggXHViZDg0XHViYWE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LiBcXChcXGZyYWN7YX17Yn0gPSBcXGZyYWN7NX17N31cXClcdWI3N2NcdWJhNzQsIFx1YzU0NFx1YmE1NFx1YzJhNFx1YzY0MCBcdWQ1ZThcdWI5YWNcdWM3NTggXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQwIFxcKFxcZnJhY3s1fXs3fSA9IFxcZnJhY3sxfXsyfSArIFxcZnJhY3sxfXs1fSArIFxcZnJhY3sxfXs3MH1cXCkgXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWM4YyBcdWI0MThcdWJiYzBcdWI4NWMgXHViMmY5XHVjMmUwXHVjNzU4IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0MCBcdWJjMThcdWI0ZGNcdWMyZGMgNzAgXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjUgXHViMzcwXHVjNzc0XHVkMTMwXHViMjk0IFx1ZDQ1Y1x1YzkwMFx1Yzc4NVx1YjgyNVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc0MCBUIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHViMzcwXHVjNzc0XHVkMTMwXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxY1x1YjJlNC4gXHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWIzNzBcdWM3NzRcdWQxMzBcdWM3NTggXHVhYzFjXHVjMjE4IFQgXHVhYzAwIFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHViMzcwXHVjNzc0XHVkMTMwXHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDE4XHViYTcwLCBcdWM1ZWNcdWFlMzBcdWM1ZDBcdWIyOTQgXHVjNzg1XHViODI1IFx1YmQ4NFx1YzIxOCBcXChcXGZyYWN7YX17Yn1cXClcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHViMjk0IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IFxcKGFcXClcdWM2NDAgXFwoYlxcKSAoMSAmbGU7Jm5ic3A7XFwoYVxcKSAmbHQ7IFxcKGJcXCkmbmJzcDsmbGU7Jm5ic3A7MTAsMDAwKSBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFxcKGFcXClcdWM2NDAgXFwoYlxcKVx1YjI5NCBcdWMxMWNcdWI4NWNcdWMxOGNcdWM3NzRcdWJhNzAsIFx1Yzc4NVx1YjgyNVx1YmQ4NFx1YzIxOCBcXChcXGZyYWN7YX17Yn1cXCkgXHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWM1NDRcdWJhNTRcdWMyYTRcdWM2NDAgXHVkNWU4XHViOWFjXHVjNzU4IFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1Yzc0NCBcdWMyZTRcdWQ1ODlcdWQ1ODhcdWM3NDQgXHViNTRjXHVjNWQwIFx1Y2Q5Y1x1YjgyNVx1YjQxOFx1YjI5NCBcdWIyZThcdWM3MDQgXHViZDg0XHVjMjE4XHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcXChcXGZyYWN7MX17eF8xfSxcXGZyYWN7MX17eF8yfSxcXGZyYWN7MX17eF8zfSxcXGNkb3RzLFxcZnJhY3sxfXt4X219XFwpIFx1Yjc3Y1x1YmE3NCwgXFwoYnhfMXhfMiBcXGNkb3RzIHhfe20tMX0gJmx0OyAyXnszMX1cXCkgXHVjNzU4IFx1YmQ4MFx1YjRmMVx1YzJkZFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NWNcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDljXHViODI1XHVjNzQwIFx1ZDQ1Y1x1YzkwMFx1Y2Q5Y1x1YjgyNVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHViMzcwXHVjNzc0XHVkMTMwXHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHVjODE1XHVkNjU1XHVkNzg4IFx1ZDU1YyBcdWM5MDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1OFx1YmE3MCBcdWM1ZWNcdWFlMzBcdWM1ZDBcdWIyOTQgXHVjODE1XHVjMjE4IFx1ZDU1OFx1YjA5OFx1YjljY1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWM4MTVcdWMyMThcdWIyOTQgXHVjNTQ0XHViYTU0XHVjMmE0XHVjNjQwIFx1ZDVlOFx1YjlhY1x1Yzc1OCBcdWM1NGNcdWFjZTBcdWI5YWNcdWM5OThcdWM3NDQgXHVjNzg1XHViODI1IFx1YmQ4NFx1YzIxOCBcXChcXGZyYWN7YX17Yn1cXCkgXHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWMyZTRcdWQ1ODlcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWNkOWNcdWI4MjVcdWI0MThcdWIyOTQgXHVkNWU4XHViOWFjXHVjMmRkIFx1ZDQ1Y1x1ZDYwNFx1YmM5NVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHViMmU4XHVjNzA0XHViZDg0XHVjMjE4XHVjNzU4IFx1YmQ4NFx1YmFhOFx1YzY0MCBcdWFjMTlcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjEwMjUzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSGVucnkiLCJkZXNjcmlwdGlvbiI6IjxwPkhlbnJ5LCBhIDEwIHllYXIgb2xkIGJveSwgaGFzIGp1c3QgbGVhcm5lZCBhYm91dCB0aGUgY29uY2VwdCBvZiBmcmFjdGlvbnMgdG9kYXkgZnJvbSBoaXMgbWF0aCB0ZWFjaGVyIEFobWVzLiBIZW5yeSBsaWtlZCBzbyBtdWNoIHRvIHBsYXkgd2l0aCBmcmFjdGlvbnMsIGFuZCBhbGwgb2YgYSBzdWRkZW4gZm91bmQgaXQgZnVubnkgdG8gcmVwcmVzZW50IGEgZnJhY3Rpb24gYnkgdGhlIHN1bSBvZiBkaWZmZXJlbnQgZnJhY3Rpb25zLiBIZW5yeSBoYXMgdHJpZWQgbWFueSBmcmFjdGlvbnMsIGFuZCBkaXNjb3ZlcmVkIHRoYXQgYWxsIGZyYWN0aW9ucyBoZSB0cmllZCBjYW4gYmUgcmVwcmVzZW50ZWQgYnkgYSBzdW0gb2YgZGlzdGluY3QgdW5pdCBmcmFjdGlvbnMuIEEgdW5pdCBmcmFjdGlvbiBpcyBhIGZyYWN0aW9uIHdob3NlIG51bWVyYXRvciBpcyAxLiBGb3IgZXhhbXBsZSwgXFwoXFxmcmFjezR9ezIzfVxcKSBjYW4gYmUgcmVwcmVzZW50ZWQgYXMgXFwoXFxmcmFjezF9ezZ9ICsgXFxmcmFjezF9ezEzOH1cXCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkhlbnJ5IHRvbGQgaGlzIGRpc2NvdmVyeSB0byBBaG1lcy4gQWhtZXMgd2FzIHNvIGhhcHB5IGFib3V0IHRoZSBsaXR0bGUgYm95JnJzcXVvO3MgYnJpbGxpYW50IGRpc2NvdmVyeSwgYW5kIG5hbWVkIHN1Y2ggYSByZXByZXNlbnRhdGlvbiBvZiBhIGZyYWN0aW9uIGEgSGVucnkgcmVwcmVzZW50YXRpb24uIFRoYXQgaXMsIGEgSGVucnkgcmVwcmVzZW50YXRpb24gb2YgZnJhY3Rpb24gXFwoXFxmcmFje2F9e2J9XFwpIGlzIGEgc2VyaWVzIG9mIGRpc3RpbmN0IHVuaXQgZnJhY3Rpb25zIHRoYXQgc3VtIHVwIGV4YWN0bHkgdG8gXFwoXFxmcmFje2F9e2J9XFwpLiBIZW5yeSBhbmQgQWhtZXMgY29udGludWVkIHN0dWR5aW5nIEhlbnJ5IHJlcHJlc2VudGF0aW9ucy4gQXQgbGFzdCB0aGV5IGZvdW5kIHRoYXQgZXZlcnkgZnJhY3Rpb24gdGhhdCBpcyBzbWFsbGVyIHRoYW4gMSBpbmRlZWQgaGFzIGEgSGVucnkgcmVwcmVzZW50YXRpb24gYW5kIG1heSBoYXZlIG1hbnkgZGlmZmVyZW50IG9uZXM6IGZvciBleGFtcGxlLCBcXChcXGZyYWN7NX17N30gPSBcXGZyYWN7MX17Mn0gKyBcXGZyYWN7MX17NX0gKyBcXGZyYWN7MX17NzB9ID0gXFxmcmFjezF9ezJ9K1xcZnJhY3sxfXs2fSArIFxcZnJhY3sxfXsyMX0gPSBcXGZyYWN7MX17Mn0gKyBcXGZyYWN7MX17N30gKyBcXGZyYWN7MX17MTR9XFwpLiBBbHNvLCBub3RpY2UgYnkgZGVmaW5pdGlvbiB0aGF0IFxcKFxcZnJhY3syfXszfSA9IFxcZnJhY3sxfXszfSArIFxcZnJhY3sxfXszfVxcKSBpcyBub3QgYSBIZW5yeSByZXByZXNlbnRhdGlvbiBiZWNhdXNlIHRoYXQgY29udGFpbnMgdHdvIGVxdWFsIHVuaXQgZnJhY3Rpb25zIFxcKFxcZnJhY3sxfXszfVxcKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QWhtZXMgYW5kIEhlbnJ5IGFsc28gZm91bmQgYW4gZWFzeSBwcm9jZWR1cmUgdG8gZmluZCBhIEhlbnJ5IHJlcHJlc2VudGF0aW9uIG9mIGEgZ2l2ZW4gZnJhY3Rpb24sIGRlc2NyaWJlZCBhcyBmb2xsb3dzOiBnaXZlbiBhIGZyYWN0aW9uIFxcKFxcZnJhY3thfXtifVxcKSB3aGVyZSBcXChhXFwpIGFuZCBcXChiXFwpIGFyZSBwb3NpdGl2ZSBpbnRlZ2VycyB3aXRoIFxcKGEgJmx0OyBiXFwpLCBjaG9vc2UgdGhlIGxhcmdlc3QgdW5pdCBmcmFjdGlvbiBcXChcXGZyYWN7MX17eF8xfVxcKSBzdWNoIHRoYXQgXFwoXFxmcmFjezF9e3hfMX0gXFxsZSBcXGZyYWN7YX17Yn1cXCkuIFRoZW4sIHN1YnRyYWN0IFxcKFxcZnJhY3sxfXt4XzF9XFwpIGZyb20gXFwoXFxmcmFje2F9e2J9XFwpLCBhbmQgcmVwZWF0IHRoZSBwcm9jZXNzIGZvciB0aGUgcmVtYWluZGVyOiBjaG9vc2UgdGhlIGxhcmdlc3QgdW5pdCBmcmFjdGlvbiBcXChcXGZyYWN7MX17eF8yfVxcKSBzdWNoIHRoYXQgXFwoXFxmcmFjezF9e3hfMn0gXFxsZSBcXGZyYWN7YX17Yn0gLSBcXGZyYWN7MX17eF8xfVxcKS4gUmVwZWF0IGFnYWluIHVudGlsIHRoZXJlIGlzIG5vIHJlbWFpbmRlci4gVGhpcyBwcm9jZWR1cmUgd2lsbCByZXN1bHQgaW4gYSBzZXJpZXMgb2YgdW5pdCBmcmFjdGlvbnMgXFwoXFxmcmFjezF9e3hfMX0sIFxcZnJhY3sxfXt4XzJ9LCBcXGZyYWN7MX17eF8zfSwgXFxkb3RzXFwpIHRoYXQgc3VtIHVwIHRvIHRoZSBnaXZlbiBmcmFjdGlvbiBcXChcXGZyYWN7YX17Yn1cXCkuIEFobWVzIGFuZCBIZW5yeSBwcm92ZWQgdGhhdCB0aGlzIHByb2NlZHVyZSBhbHdheXMgdGVybWluYXRlcyBmb3IgYW55IGlucHV0IGZyYWN0aW9uIFxcKFxcZnJhY3thfXtifVxcKSB3aXRoIGEgZmluaXRlIG51bWJlciBvZiBkaXN0aW5jdCB1bml0IGZyYWN0aW9ucywgdGhhdCBpcywgYSBIZW5yeSByZXByZXNlbnRhdGlvbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QWhtZXMgYW5kIEhlbnJ5IHdhbnQgdG8gaGF2ZSB0aGVpciBhbGdvcml0aG0gaW1wbGVtZW50ZWQgYnkgeW91LiBHaXZlbiBhIGZyYWN0aW9uIFxcKFxcZnJhY3thfXtifVxcKSwgeW91IGFyZSB0byB3cml0ZSBhIGNvbXB1dGVyIHByb2dyYW0gdGhhdCBwcmludHMgb3V0IHRoZSBkZW5vbWluYXRvciBvZiB0aGUgbGFzdCBmcmFjdGlvbiBpbiB0aGUgcmVzdWx0aW5nIEhlbnJ5IHJlcHJlc2VudGF0aW9uIG9mIHRoZWlyIGFsZ29yaXRobS4gRm9yIGV4YW1wbGUsIGlmIFxcKFxcZnJhY3thfXtifSA9IFxcZnJhY3s1fXs3fVxcKSwgdGhlbiB5b3VyIHByb2dyYW0gbXVzdCBwcmludCBvdXQgNzAgc2luY2UgdGhlIGFsZ29yaXRobSB3aWxsIHRlcm1pbmF0ZSB3aXRoIGEgSGVucnkgcmVwcmVzZW50YXRpb24gXFwoXFxmcmFjezV9ezd9ID0gXFxmcmFjezF9ezJ9ICsgXFxmcmFjezF9ezV9ICsgXFxmcmFjezF9ezcwfVxcKS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgYSBsaW5lIGNvbnRhaW5pbmcgdHdvIGludGVnZXJzIFxcKGFcXCkgYW5kIFxcKGJcXCkgKCAxICZsZTsgXFwoYVxcKSAmbHQ7IFxcKGJcXCkgJmxlOyAxMCwwMDAgKSB0aGF0IGFyZSByZWxhdGl2ZWx5IHByaW1lLCByZXByZXNlbnRpbmcgdGhlIGlucHV0IGZyYWN0aW9uIFxcKFxcZnJhY3thfXtifVxcKS4gTm90ZSB0aGF0IGlmIFxcKFxcZnJhY3sxfXt4XzF9LFxcZnJhY3sxfXt4XzJ9LFxcZnJhY3sxfXt4XzN9LFxcY2RvdHMsXFxmcmFjezF9e3hfbX1cXCkgYXJlIHRoZSB1bml0IGZyYWN0aW9ucyBwcm9kdWNlZCBieSBBaG1lcyBhbmQgSGVucnkmcnNxdW87cyBhbGdvcml0aG0gaW4gb3JkZXIgZm9yIHRoZSBpbnB1dCBcXChcXGZyYWN7YX17Yn1cXCksIHRoZW4geW91IGNhbiBhc3N1bWUgdGhhdCAmbmJzcDtcXChieF8xeF8yIFxcY2RvdHMgeF97bS0xfSAmbHQ7IDJeezMxfVxcKSAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHdyaXRlIHRvIHN0YW5kYXJkIG91dHB1dC4gUHJpbnQgZXhhY3RseSBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNhc2UuIFRoZSBsaW5lIHNob3VsZCBjb250YWluIGFuIGludGVnZXIgcmVwcmVzZW50aW5nIHRoZSBkZW5vbWluYXRvciBvZiB0aGUgbGFzdCBmcmFjdGlvbiBpbiB0aGUgcmVzdWx0aW5nIEhlbnJ5IHJlcHJlc2VudGF0aW9uIG9mIEFobWVzIGFuZCBIZW5yeSZyc3F1bztzIGFsZ29yaXRobSBmb3IgdGhlIGlucHV0IGZyYWN0aW9uIFxcKFxcZnJhY3thfXtifVxcKTxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Asia Pacific > Korea > Nationwide Internet Competition > Daejeon Nationalwide Internet Competition 2014 D번