시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB100522164158822.145%

문제

창영이는 선영이가 사탕을 공평하게 나누어주지 않으면 친구들을 때릴정도로 사탕을 좋아한다.

따라서, 선영이는 다음 파티에 사용할 사탕을 구매하기 전에 고민을 하기 시작했다.

만약 파티에 K명이 참가한다면, 공정하게 나누어주려면 K×X개를 사야 한다. (X는 자연수) 

선영이는 항상 적어도 한 아이는 사탕을 잃어버린다는 사실을 알고 있다. 그래서 캔디를 하나 더 구매해 총 (K×X+1)개를 구매하려고 한다.

사탕은 봉지 단위로 판매한다. 한 봉지에는 사탕이 총 C개 들어있다. 문제의 조건을 만족하면서 구매할 수 있는 사탕 봉지의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (0 < t < 100) 각 테스트 케이스는 한 줄로 이루어져 있고, K와 C가 공백으로 구분되어져서 주어진다. (1 ≤ K, C ≤ 109) 선영이는 부자가 아니기 때문에 109개를 넘는 사탕 봉지를 구매하지 못한다.

출력

각 테스트 케이스에 대해서 문제의 조건을 만족시키면서 구매할 수 있는 사탕 봉지가 없다면, "IMPOSSIBLE"을 출력한다. 이 경우가 아닌 경우에는 선영이가 구매해야 하는 사탕 봉지의 수를 출력한다. 만약, 가능한 봉지의 수가 여러개라면 아무거나 출력한다.

예제 입력 1

5
10 5
10 7
1337 23
123454321 42
999999937 142857133

예제 출력 1

IMPOSSIBLE
3
872
14696943
166666655
W3sicHJvYmxlbV9pZCI6IjM5NTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlOTRcdWI1MTQgXHViZDg0XHViYzMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHVjMTIwXHVjNjAxXHVjNzc0XHVhYzAwIFx1YzBhY1x1ZDBkNVx1Yzc0NCBcdWFjZjVcdWQzYzlcdWQ1NThcdWFjOGMgXHViMDk4XHViMjA0XHVjNWI0XHVjOGZjXHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NCBcdWNlNWNcdWFkNmNcdWI0ZTRcdWM3NDQgXHViNTRjXHViOWI0XHVjODE1XHViM2M0XHViODVjIFx1YzBhY1x1ZDBkNVx1Yzc0NCBcdWM4OGJcdWM1NDRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YjJlNFx1Yzc0YyBcdWQzMGNcdWQyZjBcdWM1ZDAgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YzBhY1x1ZDBkNVx1Yzc0NCBcdWFkNmNcdWI5ZTRcdWQ1NThcdWFlMzAgXHVjODA0XHVjNWQwIFx1YWNlMFx1YmJmY1x1Yzc0NCBcdWQ1NThcdWFlMzAgXHVjMmRjXHVjNzkxXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QgXHVkMzBjXHVkMmYwXHVjNWQwIEtcdWJhODVcdWM3NzQgXHVjYzM4XHVhYzAwXHVkNTVjXHViMmU0XHViYTc0LCBcdWFjZjVcdWM4MTVcdWQ1NThcdWFjOGMgXHViMDk4XHViMjA0XHVjNWI0XHVjOGZjXHViODI0XHViYTc0IEsmdGltZXM7WFx1YWMxY1x1Yjk3YyBcdWMwYWNcdWM1N2MgXHVkNTVjXHViMmU0LiAoWFx1YjI5NCBcdWM3OTBcdWM1ZjBcdWMyMTgpJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWQ1NmRcdWMwYzEgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1YyBcdWM1NDRcdWM3NzRcdWIyOTQgXHVjMGFjXHVkMGQ1XHVjNzQ0IFx1Yzc4M1x1YzViNFx1YmM4NFx1YjliMFx1YjJlNFx1YjI5NCBcdWMwYWNcdWMyZTRcdWM3NDQgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1Y2U5NFx1YjUxNFx1Yjk3YyBcdWQ1NThcdWIwOTggXHViMzU0IFx1YWQ2Y1x1YjllNFx1ZDU3NCBcdWNkMWQgKEsmdGltZXM7WCsxKVx1YWMxY1x1Yjk3YyBcdWFkNmNcdWI5ZTRcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYWNcdWQwZDVcdWM3NDAgXHViZDA5XHVjOWMwIFx1YjJlOFx1YzcwNFx1Yjg1YyBcdWQzMTBcdWI5ZTRcdWQ1NWNcdWIyZTQuIFx1ZDU1YyBcdWJkMDlcdWM5YzBcdWM1ZDBcdWIyOTQgXHVjMGFjXHVkMGQ1XHVjNzc0IFx1Y2QxZCBDXHVhYzFjIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjJlNC4gXHViYjM4XHVjODFjXHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWJhNzRcdWMxMWMgXHVhZDZjXHViOWU0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMGFjXHVkMGQ1IFx1YmQwOVx1YzljMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IHRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbHQ7IHQgJmx0OyAxMDApIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgS1x1YzY0MCBDXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjRcdWM4MzhcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEssIEMgJmxlOyAxMDxzdXA+OTxcL3N1cD4pIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWJkODBcdWM3OTBcdWFjMDAgXHVjNTQ0XHViMmM4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCAxMDxzdXA+OTxcL3N1cD5cdWFjMWNcdWI5N2MgXHViMTE4XHViMjk0IFx1YzBhY1x1ZDBkNSBcdWJkMDlcdWM5YzBcdWI5N2MgXHVhZDZjXHViOWU0XHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHViYjM4XHVjODFjXHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWMyZGNcdWQwYTRcdWJhNzRcdWMxMWMgXHVhZDZjXHViOWU0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMGFjXHVkMGQ1IFx1YmQwOVx1YzljMFx1YWMwMCBcdWM1YzZcdWIyZTRcdWJhNzQsICZxdW90O0lNUE9TU0lCTEUmcXVvdDtcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YzU0NFx1YjJjYyBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjMTIwXHVjNjAxXHVjNzc0XHVhYzAwIFx1YWQ2Y1x1YjllNFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjMGFjXHVkMGQ1IFx1YmQwOVx1YzljMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWJkMDlcdWM5YzBcdWM3NTggXHVjMjE4XHVhYzAwIFx1YzVlY1x1YjdlY1x1YWMxY1x1Yjc3Y1x1YmE3NCBcdWM1NDRcdWJiMzRcdWFjNzBcdWIwOTggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjM5NTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDYW5keSBEaXN0cmlidXRpb24iLCJkZXNjcmlwdGlvbiI6IjxwPktpZHMgbGlrZSBjYW5kaWVzLCBzbyBtdWNoIHRoYXQgdGhleSBzdGFydCBiZWF0aW5nIGVhY2ggb3RoZXIgaWYgdGhlIGNhbmRpZXMgYXJlIG5vdCBmYWlybHkgZGlzdHJpYnV0ZWQuIFNvIG9uIHlvdXIgbmV4dCBwYXJ0eSwgeW91IGJldHRlciBzdGFydCB0aGlua2luZyBiZWZvcmUgeW91IGJ1eSB0aGUgY2FuZGllcy48XC9wPlxyXG5cclxuPHA+SWYgdGhlcmUgYXJlIEsga2lkcywgd2Ugb2YgY291cnNlIG5lZWQgSyAmdGltZXM7IFggY2FuZGllcyBmb3IgYSBmYWlyIGRpc3RyaWJ1dGlvbiwgd2hlcmUgWCBpcyBhIHBvc2l0aXZlIG5hdHVyYWwgbnVtYmVyLiBCdXQgd2UgbGVhcm5lZCB0aGF0IGFsd2F5cyBhdCBsZWFzdCBvbmUga2lkIGxvb3NlcyBvbmUgY2FuZHksIHNvIGJldHRlciBiZSBwcmVwYXJlZCB3aXRoIGV4YWN0bHkgb25lIHNwYXJlIGNhbmR5LCByZXN1bHRpbmcgaW4gKEsgJnRpbWVzOyBYKSArIDEgY2FuZGllcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VXN1YWxseSwgdGhlIGNhbmRpZXMgYXJlIHBhY2tlZCBpbnRvIGJhZ3Mgd2l0aCBhIGZpeGVkIG51bWJlciBvZiBjYW5kaWVzIEMuIFdlIHdpbGwgYnV5IHNvbWUgb2YgdGhlc2UgYmFncyBzbyB0aGF0IHRoZSBhYm92ZSBjb25zdHJhaW50cyBhcmUgZnVsIGxsZWQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmkgcnN0IGxpbmUgZ2l2ZXMgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIHQgKDAgJmx0OyB0ICZsdDsgMTAwKS4gRWFjaCB0ZXN0IGNhc2UgaXMgc3BlY2kgZWQgYnkgdHdvIGludGVnZXJzIEsgYW5kIEMgb24gYSBzaW5nbGUgbGluZSwgd2hlcmUgSyBpcyB0aGUgbnVtYmVyIG9mIGtpZHMgYW5kIEMgdGhlIG51bWJlciBvZiBjYW5kaWVzIGluIG9uZSBiYWcgKDEgJmxlOyBLLCBDICZsZTsgMTA8c3VwPjk8XC9zdXA+KS4gQXMgeW91IG1vbmV5IGlzIGxpbWl0ZWQsIHlvdSB3aWxsIG5ldmVyIGJ1eSBtb3JlIHRoYW4gMTA8c3VwPjk8XC9zdXA+IGNhbmR5IGJhZ3MuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCBvbmUgbGluZS4gSWYgdGhlcmUgaXMgbm8gc3VjaCBudW1iZXIgb2YgY2FuZHkgYnVncyB0byBmdWwgbGwgdGhlIGFib3ZlIGNvbnN0cmFpbnRzLCBwcmludCAmcXVvdDtJTVBPU1NJQkxFJnF1b3Q7IGluc3RlYWQuIE90aGVyd2lzZSBwcmludCB0aGUgbnVtYmVyIG9mIGNhbmR5IGJhZ3MsIHlvdSB3YW50IHRvIGJ1eS4gSWYgdGhlcmUgaXMgbW9yZSB0aGFuIG9uZSBzb2x1dGlvbiwgYW55IHdpbGwgZG8uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > German Collegiate Programming Contest > GCPC 2012 C번

  • 문제를 번역한 사람: baekjoon
  • 데이터를 추가한 사람: lyzqm