시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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
W3sicHJvYmxlbV9pZCI6IjExMzA5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkMzBjXHVjNmNjISFcdWIyZWNcdWFjNDAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzc5OFx1YzBkZFx1YWUzNCBcdWM2MjRcdWM3NzQgXHViY2EwXHViMTI0XHViNTE1XHVkMmI4XHViMjk0IFx1Y2ZlMFx1ZDMyMVx1YzVkMFx1YzExYyZuYnNwO0tcdWFjMWNcdWM3NTggXHViM2Q5XHVjNzdjXHVkNTVjJm5ic3A7XHVkMzBjXHVjNmNjISFcdWIyZWNcdWFjNDBcdWM3NDQgXHVhZDZjXHViOWU0XHVkNTg4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhZGY4XHViMjk0IFx1YzU0NVx1YjNjNVx1ZDU1YyBcdWFjNzRcdWJiM2NcdWM4ZmNcdWI3N2NcdWMxMWMsIFx1YWMxMVx1Yzc5MFx1YWUzMCZuYnNwO1x1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjZTM1XHVjNWQwXHVjMTFjIFx1YzdhY1x1YmJmOFx1YzBiY1x1YzU0NCZuYnNwO1x1YjJlY1x1YWM0MFx1Yzc0NCBcdWI1YThcdWFkODhcdWJjZjRcdWFjZTAgXHVjMmY2XHVjNWI0XHVjODRjXHViMmU0LiBcdWFkZjhcdWM3NTggXHVhYzc0XHViYjNjXHVjNzQwIDFcdWM1ZDBcdWMxMWMgTlx1YWU0Y1x1YzljMCBcdWNlMzVcdWMyMThcdWFjMDAgXHViOWU0XHVhY2E4XHVjOWM0LCBcdWNkMWQgTlx1Y2UzNSBcdWIxOTJcdWM3NzRcdWM3NTgmbmJzcDtcdWFjNzRcdWJiM2NcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YmNhMFx1YjEyNFx1YjUxNVx1ZDJiOFx1YWMwMCBcdWFkNmNcdWI5ZTRcdWQ1NWMgXHViMmVjXHVhYzQwXHVjNzQwIFx1ZDMwY1x1YzZjYyEhXHViMmVjXHVhYzQwXHVjNzc0XHViNzdjXHVjMTFjLCBcdWQyYjlcdWM4MTUgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU3NFx1YzU3Y1x1YjljYyBcdWFlNjhcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWIyZWNcdWFjNDBcdWM3NDAgRisxIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWNlMzVcdWM1ZDBcdWMxMWMgXHViNWE4XHVhZDg4XHVjOWMwXHViYTc0IFx1YWU2OFx1YzljMFx1YzljMFx1YjljYywgRiBcdWM3NzRcdWQ1NThcdWM3NTggXHVjZTM1XHVjNWQwXHVjMTFjIFx1YjVhOFx1YWQ4OFx1YzljMFx1YmE3NCBcdWFlNjhcdWM5YzBcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gKEZcdWIyOTQgMFx1YzVkMFx1YzExYyBOIFx1YzBhY1x1Yzc3NCBcdWMyMmJcdWM3OTAgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YjJlNC4pPFwvcD5cclxuXHJcbjxwPlx1YmNhMFx1YjEyNFx1YjUxNVx1ZDJiOFx1YjI5NCBcdWIyZWNcdWFjNDBcdWM3NzQgXHVhZTY4XHVjOWM4IFx1YjU0Y1x1YWU0Y1x1YzljMCwgXHVhZGY4XHVhYzAwIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWQ2OWZcdWMyMThcdWI5Y2NcdWQwN2MgXHVjNmQwXHVkNTU4XHViMjk0IFx1Y2UzNVx1YzVkMFx1YzExYyBcdWI1YThcdWFkNzQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViMjk0IEZcdWI5N2MgXHVkNjU1XHVjODE1XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWNkNWNcdWMxOGNcdWQ1NWMgXHViYTg3IFx1YmM4OCZuYnNwO1x1YjJlY1x1YWM0MFx1Yzc0NCBcdWI1YThcdWM1YjRcdWI3MjhcdWI4MjRcdWM1N2MgXHVkNTU4XHViMjk0XHVjOWMwIFx1YzU0Y1x1YWNlMCBcdWMyZjZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjRcdWMxMWMsIFx1YjljY1x1YzU3ZCBcdWJjYTBcdWIxMjRcdWI1MTVcdWQyYjhcdWM3NTggXHVhYzc0XHViYjNjXHVjNzc0IDNcdWNlMzUgXHVjOWRjXHViOWFjXHVjNzc0XHVhY2UwLCZuYnNwO1x1YmNhMFx1YjEyNFx1YjUxNVx1ZDJiOFx1YWMwMCBcdWIyZWNcdWFjNDBcdWM3NDQgXHVkNTU4XHViMDk4XHViOWNjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTc0XHViY2Y0XHVjNzkwLiBcdWNjOThcdWM3NGNcdWM1ZDAgXHVhZGY4XHViMjk0IFx1Y2NhYlx1YmM4OFx1YzlmOCBcdWNlMzVcdWM1ZDBcdWMxMWMgXHViMmVjXHVhYzQwXHVjNzQ0IFx1YjVhOFx1YzViNFx1YjcyOFx1YjgyNFx1YmNmNFx1YzU0NFx1YzU3YyBcdWQ1NThcdWFjZTAsIFx1YWRmOFx1YjdmMCBcdWIyZTRcdWM3NGNcdWM1ZDAmbmJzcDtcdWI0NTAgXHViYzg4XHVjOWY4IFx1Y2UzNVx1YzVkMFx1YzExYyhcdWI5Y2NcdWM1N2QgXHViMmVjXHVhYzQwXHVjNzc0IFx1YmIzNFx1YzBhY1x1ZDU1OFx1YjJlNFx1YmE3NCBcdWI5ZDBcdWM3NzRcdWIyZTQpLCBcdWFkZjhcdWI3ZjAgXHViMmU0XHVjNzRjIFx1YjJlNFx1YzJkYyBcdWMxMzggXHViYzg4XHVjOWY4IFx1Y2UzNVx1YzVkMFx1YzExYyhcdWM1ZWRcdWMyZGNcdWIwOTggXHViOWNjXHVjNTdkIFx1YjJlY1x1YWM0MFx1Yzc3NCBcdWJiMzRcdWMwYWNcdWQ1NThcdWIyZTRcdWJhNzQpIFx1YjVhOFx1YzViNFx1YjcyOFx1YjgyNFx1YmNmNFx1YzU0NFx1YzU3YyBcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWFkZjhcdWI3ZWNcdWJiYzBcdWI4NWMsIFx1Y2Q1Y1x1YzU0NVx1Yzc1OCBcdWFjYmRcdWM2YjBcdWI5N2MgXHVhY2UwXHViODI0XHVkNTc0XHViY2ZjIFx1YjU0YyBcdWNkNWNcdWMxOGNcdWQ1NWMmbmJzcDtcdWMxMzggXHViYzg4XHVjNzQwIFx1YjVhOFx1YzViNFx1YjcyOFx1YjgyNCBcdWJjZjRcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjMmU0XHVkNTg5XHVkNjlmXHVjMjE4XHVjNzc4Jm5ic3A7VFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAmbmJzcDsoMSAmbGU7IFQgJmxlOyAxMDAwMCksIFx1YjRhNFx1Yzc3NFx1YzViNCZuYnNwO1RcdWFjMWNcdWM3NTggXHVjOTA0XHVjNzc0IFx1Yzc3NFx1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzIyYlx1Yzc5MCA6Jm5ic3A7XHVhYzc0XHViYjNjXHVjNzU4IFx1YjE5Mlx1Yzc3NCBOXHVhY2ZjIFx1YjJlY1x1YWM0MFx1Yzc1OCBcdWFjMWNcdWMyMTggS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7KDEgJmxlOyBOICZsZTsgMjAwMDAwMDAwNywmbmJzcDsxICZsZTsgSyAmbGU7IDMyKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRcdWFjMWNcdWM3NTggXHVhYzAxIFx1YzkwNFx1YzVkMFx1YjI5NCwgRlx1Yjk3YyBcdWQ2NTVcdWM4MTVcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YjJlY1x1YWM0MFx1Yzc0NCBcdWI1YThcdWFkODhcdWM1N2MgXHVkNTU4XHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YjljY1x1YzU3ZCBcdWFkZjggXHVkNjlmXHVjMjE4XHVhYzAwIDMyXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YjJlNFx1YmE3NCwgSW1wb3NzaWJsZVx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YmQ4OFx1YzMwZFx1ZDU1OFx1YWNlMFx1YjNjNCBcdWFjMDBcdWM1ZmVcdWM3NDAgXHVjNmIwXHViOWFjIFx1YmNhMFx1YjEyNFx1YjUxNVx1ZDJiOFx1YjI5NCwgXHVhZGY4XHViODA3XHVhYzhjIFx1YjljZVx1Yzc3NCBcdWIyZWNcdWFjNDBcdWM3NDQgXHViNWE4XHVjNWI0XHViNzI4XHViOWFjXHVhY2UwXHViMjk0IFx1YjEwOFx1YmIzNFx1YjNjNCBcdWQ3OThcdWI0ZTRcdWM1YjRcdWMxMWMgXHViMzU0XHViMjk0IFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWM5YzBcdWMxOGRcdWQ1NjAgXHVjMjE4XHVhYzAwIFx1YzVjNlx1YjJlNC4gXHVjNzc0XHVkNTU4IFx1Yzc5MVx1YzVjNVx1Yzc0MCBcdWMwZGRcdWI3YjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTEzMDkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQb3dlciBFZ2dzIiwiZGVzY3JpcHRpb24iOiI8cD5CZW5lZGljdCBib3VnaHQgSyBpZGVudGljYWwgcG93ZXIgZWdncyBmcm9tIERyb3BlZ2dzLmNvbSwgYW5kIG5vdyBoZSB3YW50cyB0byB0ZXN0IHRoZW0gYnkgZHJvcHBpbmcgdGhlbSBmcm9tIGRpZmZlcmVudCBmbG9vcnMgb2YgaGlzIGJ1aWxkaW5nLiBIaXMgYnVpbGRpbmcgaGFzIE4gZmxvb3JzIG51bWJlcmVkIDEgdG8gTi4gRiBpcyBhbiB1bmtub3duIG51bWJlciBpbiB0aGUgcmFuZ2UgZnJvbSAwIHRvIE4sIGluY2x1c2l2ZS4gRWFjaCBlZ2cgd2lsbCBicmVhayBpZiBkcm9wcGVkIGZyb20gZmxvb3IgRisxIG9yIGFib3ZlLCBidXQgd2lsbCBub3QgYnJlYWsgaWYgZHJvcHBlZCBmcm9tIGZsb29yIEYgb3IgYmVsb3cuIEJlbmVkaWN0IGNhbiBkcm9wIGVhY2ggZWdnIGFzIG1hbnkgdGltZXMgYXMgaGUgd2FudHMgZnJvbSBhbnkgZmxvb3IgdW50aWwgaXQgYnJlYWtzLiBIZSB3YW50cyB0byBrbm93IHRoZSBtaW5pbXVtIG51bWJlciBvZiBlZ2cgZHJvcHMgbmVjZXNzYXJ5IHRvIGVuc3VyZSB0aGF0IGhlIGNhbiBkZXRlcm1pbmUgRi48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGlmIHRoZXJlIGFyZSB0aHJlZSBmbG9vcnMgYW5kIEJlbmVkaWN0IGhhcyBvbmx5IG9uZSBlZ2csIHRoZW4gaGUgaGFzIHRvIGZpcnN0IHRocm93IHRoZSBlZ2cgZnJvbSB0aGUgZmlyc3QgZmxvb3IsIHRoZW4gZnJvbSB0aGUgc2Vjb25kIGZsb29yIChpZiB0aGUgZWdnIHN1cnZpdmVkKSwgYW5kIHRoZW4gZnJvbSB0aGUgdGhpcmQgZmxvb3IgKGlmIHRoZSBlZ2cgc3Vydml2ZWQpLiBUaGVyZWZvcmUsIHRocmVlIGRyb3BzIGFyZSByZXF1aXJlZCBpbiB0aGUgd29yc3QgY2FzZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIG9uZSBudW1iZXIgVCAoMSAmbGU7IFQgJmxlOyAxMDAwMCkgd2hpY2ggaXMgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLCBmb2xsb3dlZCBieSBUIGxpbmVzLiBFYWNoIG9mIHRoZSBuZXh0IFQgbGluZXMgY29udGFpbnMgdHdvIG51bWJlcnM6IE4sIHRoZSBudW1iZXIgb2YgZmxvb3JzICgxICZsZTsgTiAmbGU7IDIwMDAwMDAwMDcpIGFuZCBLLCB0aGUgbnVtYmVyIG9mIGVnZ3MgKDEgJmxlOyBLICZsZTsgMzIpLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIG9mIHRoZSBUIGxpbmVzLCBwcmludCB0aGUgbWluaW1hbCBudW1iZXIgb2YgZHJvcHMgcmVxdWlyZWQsIG9yIGlmIGl0JiMzOTtzIGdyZWF0ZXIgdGhhbiAzMiwgcHJpbnQgdGhlIHdvcmQgSW1wb3NzaWJsZS4gQWZ0ZXIgdGhhdCBtYW55IGRyb3BzLCBCZW5lZGljdCBnZXRzIHRvbyB0aXJlZCBhbmQgY2Fubm90IGNvbnRpbnVlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==