시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 44 14 7 41.176%

문제

잘생긴 오이 베네딕트는 쿠팡에서 K개의 동일한 파워!!달걀을 구매했다. 그리고 그는 악독한 건물주라서, 갑자기 서로 다른 층에서 재미삼아 달걀을 떨궈보고 싶어졌다. 그의 건물은 1에서 N까지 층수가 매겨진, 총 N층 높이의 건물이다. 

베네딕트가 구매한 달걀은 파워!!달걀이라서, 특정 조건을 만족해야만 깨진다. 각 달걀은 F+1 이상의 층에서 떨궈지면 깨지지만, F 이하의 층에서 떨궈지면 깨지지 않는다고 한다. (F는 0에서 N 사이 숫자 중 하나이다.)

베네딕트는 달걀이 깨질 때까지, 그가 원하는 횟수만큼 원하는 층에서 떨굴 수 있다. 그는 F를 확정하기 위해 최소한 몇 번 달걀을 떨어뜨려야 하는지 알고 싶다.

예를 들어서, 만약 베네딕트의 건물이 3층 짜리이고, 베네딕트가 달걀을 하나만 가지고 있다고 가정해보자. 처음에 그는 첫 번째 층에서 달걀을 떨어뜨려보아야 하고, 그런 다음에 두 번째 층에서(만약 달걀이 무사하다면 말이다), 그런 다음 다시 세 번째 층에서(역시나 만약 달걀이 무사하다면) 떨어뜨려보아야 할 것이다. 그러므로, 최악의 경우를 고려해볼 때 최소한 세 번은 떨어뜨려 보아야 한다.

입력

첫 번째 줄에는 테스트 실행횟수인 T가 주어지고 (1 ≤ T ≤ 10000), 뒤이어 T개의 줄이 이어진다.

각 줄에는 두 개의 숫자 : 건물의 높이 N과 달걀의 개수 K가 주어진다. (1 ≤ N ≤ 2000000007, 1 ≤ K ≤ 32)

출력

T개의 각 줄에는, F를 확정하기 위해 달걀을 떨궈야 하는 최소횟수를 출력한다. 

만약 그 횟수가 32보다 크다면, Impossible이라고 출력한다. 불쌍하고도 가엾은 우리 베네딕트는, 그렇게 많이 달걀을 떨어뜨리고는 너무도 힘들어서 더는 작업을 지속할 수가 없다. 이하 작업은 생략한다.

예제 입력 1

4
10 1
100 2
30 30
2000000000 2

예제 출력 1

10
14
5
Impossible
W3sicHJvYmxlbV9pZCI6IjExMzA5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkMzBjXHVjNmNjISFcdWIyZWNcdWFjNDAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzc5OFx1YzBkZFx1YWUzNCBcdWM2MjRcdWM3NzQgXHViY2EwXHViMTI0XHViNTE1XHVkMmI4XHViMjk0IFx1Y2ZlMFx1ZDMyMVx1YzVkMFx1YzExYyZuYnNwO0tcdWFjMWNcdWM3NTggXHViM2Q5XHVjNzdjXHVkNTVjJm5ic3A7XHVkMzBjXHVjNmNjISFcdWIyZWNcdWFjNDBcdWM3NDQgXHVhZDZjXHViOWU0XHVkNTg4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhZGY4XHViMjk0IFx1YzU0NVx1YjNjNVx1ZDU1YyBcdWFjNzRcdWJiM2NcdWM4ZmNcdWI3N2NcdWMxMWMsIFx1YWMxMVx1Yzc5MFx1YWUzMCZuYnNwO1x1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjZTM1XHVjNWQwXHVjMTFjIFx1YzdhY1x1YmJmOFx1YzBiY1x1YzU0NCZuYnNwO1x1YjJlY1x1YWM0MFx1Yzc0NCBcdWI1YThcdWFkODhcdWJjZjRcdWFjZTAgXHVjMmY2XHVjNWI0XHVjODRjXHViMmU0LiBcdWFkZjhcdWM3NTggXHVhYzc0XHViYjNjXHVjNzQwIDFcdWM1ZDBcdWMxMWMgTlx1YWU0Y1x1YzljMCBcdWNlMzVcdWMyMThcdWFjMDAgXHViOWU0XHVhY2E4XHVjOWM0LCBcdWNkMWQgTlx1Y2UzNSBcdWIxOTJcdWM3NzRcdWM3NTgmbmJzcDtcdWFjNzRcdWJiM2NcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YmNhMFx1YjEyNFx1YjUxNVx1ZDJiOFx1YWMwMCBcdWFkNmNcdWI5ZTRcdWQ1NWMgXHViMmVjXHVhYzQwXHVjNzQwIFx1ZDMwY1x1YzZjYyEhXHViMmVjXHVhYzQwXHVjNzc0XHViNzdjXHVjMTFjLCBcdWQyYjlcdWM4MTUgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU3NFx1YzU3Y1x1YjljYyBcdWFlNjhcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWIyZWNcdWFjNDBcdWM3NDAgRisxIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWNlMzVcdWM1ZDBcdWMxMWMgXHViNWE4XHVhZDg4XHVjOWMwXHViYTc0IFx1YWU2OFx1YzljMFx1YzljMFx1YjljYywgRiBcdWM3NzRcdWQ1NThcdWM3NTggXHVjZTM1XHVjNWQwXHVjMTFjIFx1YjVhOFx1YWQ4OFx1YzljMFx1YmE3NCBcdWFlNjhcdWM5YzBcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gKEZcdWIyOTQgMFx1YzVkMFx1YzExYyBOIFx1YzBhY1x1Yzc3NCBcdWMyMmJcdWM3OTAgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YjJlNC4pPFwvcD5cclxuXHJcbjxwPlx1YmNhMFx1YjEyNFx1YjUxNVx1ZDJiOFx1YjI5NCBcdWIyZWNcdWFjNDBcdWM3NzQgXHVhZTY4XHVjOWM4IFx1YjU0Y1x1YWU0Y1x1YzljMCwgXHVhZGY4XHVhYzAwIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWQ2OWZcdWMyMThcdWI5Y2NcdWQwN2MgXHVjNmQwXHVkNTU4XHViMjk0IFx1Y2UzNVx1YzVkMFx1YzExYyBcdWI1YThcdWFkNzQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViMjk0IEZcdWI5N2MgXHVkNjU1XHVjODE1XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWNkNWNcdWMxOGNcdWQ1NWMgXHViYTg3IFx1YmM4OCZuYnNwO1x1YjJlY1x1YWM0MFx1Yzc0NCBcdWI1YThcdWM1YjRcdWI3MjhcdWI4MjRcdWM1N2MgXHVkNTU4XHViMjk0XHVjOWMwIFx1YzU0Y1x1YWNlMCBcdWMyZjZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjRcdWMxMWMsIFx1YjljY1x1YzU3ZCBcdWJjYTBcdWIxMjRcdWI1MTVcdWQyYjhcdWM3NTggXHVhYzc0XHViYjNjXHVjNzc0IDNcdWNlMzUgXHVjOWRjXHViOWFjXHVjNzc0XHVhY2UwLCZuYnNwO1x1YmNhMFx1YjEyNFx1YjUxNVx1ZDJiOFx1YWMwMCBcdWIyZWNcdWFjNDBcdWM3NDQgXHVkNTU4XHViMDk4XHViOWNjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTc0XHViY2Y0XHVjNzkwLiBcdWNjOThcdWM3NGNcdWM1ZDAgXHVhZGY4XHViMjk0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjZTM1XHVjNWQwXHVjMTFjIFx1YjJlY1x1YWM0MFx1Yzc0NCBcdWI1YThcdWM1YjRcdWI3MjhcdWI4MjRcdWJjZjRcdWM1NDRcdWM1N2MgXHVkNTU4XHVhY2UwLCBcdWFkZjhcdWI3ZjAgXHViMmU0XHVjNzRjXHVjNWQwJm5ic3A7XHViNDUwIFx1YmM4OFx1YzlmOCBcdWNlMzVcdWM1ZDBcdWMxMWMoXHViOWNjXHVjNTdkIFx1YjJlY1x1YWM0MFx1Yzc3NCBcdWJiMzRcdWMwYWNcdWQ1NThcdWIyZTRcdWJhNzQgXHViOWQwXHVjNzc0XHViMmU0KSwgXHVhZGY4XHViN2YwIFx1YjJlNFx1Yzc0YyBcdWIyZTRcdWMyZGMgXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWNlMzVcdWM1ZDBcdWMxMWMoXHVjNWVkXHVjMmRjXHViMDk4IFx1YjljY1x1YzU3ZCBcdWIyZWNcdWFjNDBcdWM3NzQgXHViYjM0XHVjMGFjXHVkNTU4XHViMmU0XHViYTc0KSBcdWI1YThcdWM1YjRcdWI3MjhcdWI4MjRcdWJjZjRcdWM1NDRcdWM1N2MgXHVkNTYwIFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVhZGY4XHViN2VjXHViYmMwXHViODVjLCBcdWNkNWNcdWM1NDVcdWM3NTggXHVhY2JkXHVjNmIwXHViOTdjIFx1YWNlMFx1YjgyNFx1ZDU3NFx1YmNmYyBcdWI1NGMgXHVjZDVjXHVjMThjXHVkNTVjJm5ic3A7XHVjMTM4IFx1YmM4OFx1Yzc0MCBcdWI1YThcdWM1YjRcdWI3MjhcdWI4MjQgXHViY2Y0XHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWMyZTRcdWQ1ODlcdWQ2OWZcdWMyMThcdWM3NzgmbmJzcDtUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCZuYnNwOygxICZsZTsgVCAmbGU7IDEwMDAwKSwgXHViNGE0XHVjNzc0XHVjNWI0Jm5ic3A7VFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NzQgXHVjNzc0XHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwIDombmJzcDtcdWFjNzRcdWJiM2NcdWM3NTggXHViMTkyXHVjNzc0IE5cdWFjZmMgXHViMmVjXHVhYzQwXHVjNzU4IFx1YWMxY1x1YzIxOCBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsoMSAmbGU7IE4gJmxlOyAyMDAwMDAwMDA3LCZuYnNwOzEgJmxlOyBLICZsZTsgMzIpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VFx1YWMxY1x1Yzc1OCBcdWFjMDEgXHVjOTA0XHVjNWQwXHViMjk0LCBGXHViOTdjIFx1ZDY1NVx1YzgxNVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHViMmVjXHVhYzQwXHVjNzQ0IFx1YjVhOFx1YWQ4OFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjZDVjXHVjMThjXHVkNjlmXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkIFx1YWRmOCBcdWQ2OWZcdWMyMThcdWFjMDAgMzJcdWJjZjRcdWIyZTQgXHVkMDZjXHViMmU0XHViYTc0LCBJbXBvc3NpYmxlXHVjNzc0XHViNzdjXHVhY2UwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViZDg4XHVjMzBkXHVkNTU4XHVhY2UwXHViM2M0IFx1YWMwMFx1YzVmZVx1Yzc0MCBcdWM2YjBcdWI5YWMgXHViY2EwXHViMTI0XHViNTE1XHVkMmI4XHViMjk0LCBcdWFkZjhcdWI4MDdcdWFjOGMgXHViOWNlXHVjNzc0IFx1YjJlY1x1YWM0MFx1Yzc0NCBcdWI1YThcdWM1YjRcdWI3MjhcdWI5YWNcdWFjZTBcdWIyOTQgXHViMTA4XHViYjM0XHViM2M0IFx1ZDc5OFx1YjRlNFx1YzViNFx1YzExYyBcdWIzNTRcdWIyOTQgXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YzljMFx1YzE4ZFx1ZDU2MCBcdWMyMThcdWFjMDAgXHVjNWM2XHViMmU0LiBcdWM3NzRcdWQ1NTggXHVjNzkxXHVjNWM1XHVjNzQwIFx1YzBkZFx1YjdiNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMTMwOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBvd2VyIEVnZ3MiLCJkZXNjcmlwdGlvbiI6IjxwPkJlbmVkaWN0IGJvdWdodCBLIGlkZW50aWNhbCBwb3dlciBlZ2dzIGZyb20gRHJvcGVnZ3MuY29tLCBhbmQgbm93IGhlIHdhbnRzIHRvIHRlc3QgdGhlbSBieSBkcm9wcGluZyB0aGVtIGZyb20gZGlmZmVyZW50IGZsb29ycyBvZiBoaXMgYnVpbGRpbmcuIEhpcyBidWlsZGluZyBoYXMgTiBmbG9vcnMgbnVtYmVyZWQgMSB0byBOLiBGIGlzIGFuIHVua25vd24gbnVtYmVyIGluIHRoZSByYW5nZSBmcm9tIDAgdG8gTiwgaW5jbHVzaXZlLiBFYWNoIGVnZyB3aWxsIGJyZWFrIGlmIGRyb3BwZWQgZnJvbSBmbG9vciBGKzEgb3IgYWJvdmUsIGJ1dCB3aWxsIG5vdCBicmVhayBpZiBkcm9wcGVkIGZyb20gZmxvb3IgRiBvciBiZWxvdy4gQmVuZWRpY3QgY2FuIGRyb3AgZWFjaCBlZ2cgYXMgbWFueSB0aW1lcyBhcyBoZSB3YW50cyBmcm9tIGFueSBmbG9vciB1bnRpbCBpdCBicmVha3MuIEhlIHdhbnRzIHRvIGtub3cgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGVnZyBkcm9wcyBuZWNlc3NhcnkgdG8gZW5zdXJlIHRoYXQgaGUgY2FuIGRldGVybWluZSBGLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgaWYgdGhlcmUgYXJlIHRocmVlIGZsb29ycyBhbmQgQmVuZWRpY3QgaGFzIG9ubHkgb25lIGVnZywgdGhlbiBoZSBoYXMgdG8gZmlyc3QgdGhyb3cgdGhlIGVnZyBmcm9tIHRoZSBmaXJzdCBmbG9vciwgdGhlbiBmcm9tIHRoZSBzZWNvbmQgZmxvb3IgKGlmIHRoZSBlZ2cgc3Vydml2ZWQpLCBhbmQgdGhlbiBmcm9tIHRoZSB0aGlyZCBmbG9vciAoaWYgdGhlIGVnZyBzdXJ2aXZlZCkuIFRoZXJlZm9yZSwgdGhyZWUgZHJvcHMgYXJlIHJlcXVpcmVkIGluIHRoZSB3b3JzdCBjYXNlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgb25lIG51bWJlciBUICgxICZsZTsgVCAmbGU7IDEwMDAwKSB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMsIGZvbGxvd2VkIGJ5IFQgbGluZXMuIEVhY2ggb2YgdGhlIG5leHQgVCBsaW5lcyBjb250YWlucyB0d28gbnVtYmVyczogTiwgdGhlIG51bWJlciBvZiBmbG9vcnMgKDEgJmxlOyBOICZsZTsgMjAwMDAwMDAwNykgYW5kIEssIHRoZSBudW1iZXIgb2YgZWdncyAoMSAmbGU7IEsgJmxlOyAzMikuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggb2YgdGhlIFQgbGluZXMsIHByaW50IHRoZSBtaW5pbWFsIG51bWJlciBvZiBkcm9wcyByZXF1aXJlZCwgb3IgaWYgaXQmIzM5O3MgZ3JlYXRlciB0aGFuIDMyLCBwcmludCB0aGUgd29yZCBJbXBvc3NpYmxlLiBBZnRlciB0aGF0IG1hbnkgZHJvcHMsIEJlbmVkaWN0IGdldHMgdG9vIHRpcmVkIGFuZCBjYW5ub3QgY29udGludWUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d