시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 89 45 40 59.701%

문제

고전적인 '두 개의 유리 공' 문제는 다음과 같다:

두 개의 동일한 유리구가 있고, 100층 짜리 빌딩에서 유리구를 떨어뜨려서 깨지는 가장 낮은 층을 찾고 싶다. 유리구가 안깨진다면 아무런 피해가 없다고 가정하자. 어떻게 해야 (최악의 상황에서도) 가장 빨리 찾을 수 있을까?

우리가 오직 하나의 공이 있다고 가정하자. 그러면 우리는 1층부터 100층까지 차례대로 떨어뜨려보는 방법 밖에 없다.

최악의 경우는 100번만에 찾는 것이다.

이제 우리에게 두 개의 공이 있다고 하자. 그리고 첫 번째 공을 n층에서 떨어뜨린다고 하자. 만약에 그게 깨진다면 다시 공 하나가 있는 경우로 돌아가서, 1층부터 n-1층까지 시도해보면된다. 이 경우 최악의 경우 1+(n-1), 즉 n번의 시도만에 찾을 수 있다. 하지만 n층에서 깨지지 않았다면, n+1층에서 100층까지만 실험해보면 된다. 깨지거나 깨지지 않았거나 우리는 한 번의 시도를 하였다. 그래서 실험 횟수는 최악의 경우 모든 n에 대하여 가장 작다.

B개의 공과 M층 짜리 빌딩에서 최악의 경우에 몇 번 공을 떨어뜨려야 하는지를 계산하는 프로그램을 작성하시오.

입력

첫째 줄은 데이터 세트 수 P(1 ≤ P ≤ 1000)가 입력으로 들어온다. 각각의 데이터 세트는 한 줄로 구성되어 있으며 2개의 숫자가 공백으로 구분되어 있다. 유리공의 개수 B(1 ≤ B ≤ 50), 건물의 층 수 M(1 ≤ M ≤ 1000)

출력

각각의 데이터 세트에 대해 한 줄 씩, B, M에 대해 (최악의 경우에도)가장 적은 횟수의 시도 횟수를 공백으로 구분하여 출력한다.

예제 입력 1

4
2 10
2 100
2 300
25 900

예제 출력 1

4
14
24
10
W3sicHJvYmxlbV9pZCI6IjI2OTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZjUiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YWNlMFx1YzgwNFx1YzgwMVx1Yzc3OCAmIzM5O1x1YjQ1MCBcdWFjMWNcdWM3NTggXHVjNzIwXHViOWFjIFx1YWNmNSYjMzk7IFx1YmIzOFx1YzgxY1x1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0OjxcL3A+XHJcblxyXG48YmxvY2txdW90ZT5cclxuXHRcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YjNkOVx1Yzc3Y1x1ZDU1YyBcdWM3MjBcdWI5YWNcdWFkNmNcdWFjMDAgXHVjNzg4XHVhY2UwLCAxMDBcdWNlMzUgXHVjOWRjXHViOWFjIFx1YmU0Y1x1YjUyOVx1YzVkMFx1YzExYyBcdWM3MjBcdWI5YWNcdWFkNmNcdWI5N2MgXHViNWE4XHVjNWI0XHViNzI4XHViODI0XHVjMTFjIFx1YWU2OFx1YzljMFx1YjI5NCBcdWFjMDBcdWM3YTUgXHViMGFlXHVjNzQwIFx1Y2UzNVx1Yzc0NCBcdWNjM2VcdWFjZTAgXHVjMmY2XHViMmU0LiBcdWM3MjBcdWI5YWNcdWFkNmNcdWFjMDAgXHVjNTQ4XHVhZTY4XHVjOWM0XHViMmU0XHViYTc0IFx1YzU0NFx1YmIzNFx1YjdmMCBcdWQ1M2NcdWQ1NzRcdWFjMDAgXHVjNWM2XHViMmU0XHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU1OFx1Yzc5MC4gXHVjNWI0XHViNWJiXHVhYzhjIFx1ZDU3NFx1YzU3YyAoXHVjZDVjXHVjNTQ1XHVjNzU4IFx1YzBjMVx1ZDY2OVx1YzVkMFx1YzExY1x1YjNjNCkgXHVhYzAwXHVjN2E1IFx1YmU2OFx1YjlhYyBcdWNjM2VcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz88XC9ibG9ja3F1b3RlPlxyXG5cclxuPHA+XHJcblx0XHVjNmIwXHViOWFjXHVhYzAwIFx1YzYyNFx1YzljMSBcdWQ1NThcdWIwOThcdWM3NTggXHVhY2Y1XHVjNzc0IFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NThcdWM3OTAuIFx1YWRmOFx1YjdlY1x1YmE3NCBcdWM2YjBcdWI5YWNcdWIyOTQgMVx1Y2UzNVx1YmQ4MFx1ZDEzMCAxMDBcdWNlMzVcdWFlNGNcdWM5YzAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YjVhOFx1YzViNFx1YjcyOFx1YjgyNFx1YmNmNFx1YjI5NCBcdWJjMjlcdWJjOTUgXHViYzE2XHVjNWQwIFx1YzVjNlx1YjJlNC48XC9wPlxyXG48cD5cclxuXHRcdWNkNWNcdWM1NDVcdWM3NTggXHVhY2JkXHVjNmIwXHViMjk0IDEwMFx1YmM4OFx1YjljY1x1YzVkMCBcdWNjM2VcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM3NzRcdWM4MWMgXHVjNmIwXHViOWFjXHVjNWQwXHVhYzhjIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVhY2Y1XHVjNzc0IFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YWNmNVx1Yzc0NCBuXHVjZTM1XHVjNWQwXHVjMTFjIFx1YjVhOFx1YzViNFx1YjcyOFx1YjliMFx1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuIFx1YjljY1x1YzU3ZFx1YzVkMCBcdWFkZjhcdWFjOGMgXHVhZTY4XHVjOWM0XHViMmU0XHViYTc0IFx1YjJlNFx1YzJkYyBcdWFjZjUgXHVkNTU4XHViMDk4XHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWI4NWMgXHViM2NjXHVjNTQ0XHVhYzAwXHVjMTFjLCAxXHVjZTM1XHViZDgwXHVkMTMwIG4tMVx1Y2UzNVx1YWU0Y1x1YzljMCBcdWMyZGNcdWIzYzRcdWQ1NzRcdWJjZjRcdWJhNzRcdWI0MWNcdWIyZTQuIFx1Yzc3NCBcdWFjYmRcdWM2YjAgXHVjZDVjXHVjNTQ1XHVjNzU4IFx1YWNiZFx1YzZiMCAxKyhuLTEpLCBcdWM5ODkgblx1YmM4OFx1Yzc1OCBcdWMyZGNcdWIzYzRcdWI5Y2NcdWM1ZDAgXHVjYzNlXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBuXHVjZTM1XHVjNWQwXHVjMTFjIFx1YWU2OFx1YzljMFx1YzljMCBcdWM1NGFcdWM1NThcdWIyZTRcdWJhNzQsIG4rMVx1Y2UzNVx1YzVkMFx1YzExYyAxMDBcdWNlMzVcdWFlNGNcdWM5YzBcdWI5Y2MgXHVjMmU0XHVkNWQ4XHVkNTc0XHViY2Y0XHViYTc0IFx1YjQxY1x1YjJlNC4gXHVhZTY4XHVjOWMwXHVhYzcwXHViMDk4IFx1YWU2OFx1YzljMFx1YzljMCBcdWM1NGFcdWM1NThcdWFjNzBcdWIwOTggXHVjNmIwXHViOWFjXHViMjk0IFx1ZDU1YyBcdWJjODhcdWM3NTggXHVjMmRjXHViM2M0XHViOTdjIFx1ZDU1OFx1YzYwMFx1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1YzJlNFx1ZDVkOCBcdWQ2OWZcdWMyMThcdWIyOTQgXHVjZDVjXHVjNTQ1XHVjNzU4IFx1YWNiZFx1YzZiMCBcdWJhYThcdWI0ZTAgblx1YzVkMCBcdWIzMDBcdWQ1NThcdWM1ZWMgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0Qlx1YWMxY1x1Yzc1OCBcdWFjZjVcdWFjZmMgTVx1Y2UzNSBcdWM5ZGNcdWI5YWMgXHViZTRjXHViNTI5XHVjNWQwXHVjMTFjIFx1Y2Q1Y1x1YzU0NVx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHViYTg3IFx1YmM4OCBcdWFjZjVcdWM3NDQgXHViNWE4XHVjNWI0XHViNzI4XHViODI0XHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNzQwIFx1YjM3MFx1Yzc3NFx1ZDEzMCBcdWMxMzhcdWQyYjggXHVjMjE4IFAoMSAmbGU7IFAgJmxlOyAxMDAwKVx1YWMwMCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViMzcwXHVjNzc0XHVkMTMwIFx1YzEzOFx1ZDJiOFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzAgMlx1YWMxY1x1Yzc1OCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YzcyMFx1YjlhY1x1YWNmNVx1Yzc1OCBcdWFjMWNcdWMyMTggQigxICZsZTsgQiAmbGU7IDUwKSwgXHVhYzc0XHViYjNjXHVjNzU4IFx1Y2UzNSBcdWMyMTggTSgxICZsZTsgTSAmbGU7IDEwMDApPFwvcD5cclxuXHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWIzNzBcdWM3NzRcdWQxMzAgXHVjMTM4XHVkMmI4XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWQ1NWMgXHVjOTA0IFx1YzUyOSwgQiwgTVx1YzVkMCBcdWIzMDBcdWQ1NzQgKFx1Y2Q1Y1x1YzU0NVx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIzYzQpXHVhYzAwXHVjN2E1IFx1YzgwMVx1Yzc0MCBcdWQ2OWZcdWMyMThcdWM3NTggXHVjMmRjXHViM2M0IFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNjk1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmFsbHMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBjbGFzc2ljIFR3byBHbGFzcyBCYWxscyBicmFpbi10ZWFzZXIgaXMgb2Z0ZW4gcG9zZWQgYXM6Jm5ic3A7PFwvcD5cclxuXHJcbjxibG9ja3F1b3RlPlxyXG48cD4mcXVvdDtHaXZlbiB0d28gaWRlbnRpY2FsIGdsYXNzIHNwaGVyZXMsIHlvdSB3b3VsZCBsaWtlIHRvIGRldGVybWluZSB0aGUgbG93ZXN0IGZsb29yIGluIGEgMTAwLXN0b3J5IGJ1aWxkaW5nIGZyb20gd2hpY2ggdGhleSB3aWxsIGJyZWFrIHdoZW4gZHJvcHBlZC4gQXNzdW1lIHRoZSBzcGhlcmVzIGFyZSB1bmRhbWFnZWQgd2hlbiBkcm9wcGVkIGJlbG93IHRoaXMgcG9pbnQuIFdoYXQgaXMgdGhlIHN0cmF0ZWd5IHRoYXQgd2lsbCBtaW5pbWl6ZSB0aGUgd29yc3QtY2FzZSBzY2VuYXJpbyBmb3IgbnVtYmVyIG9mIGRyb3BzPyZxdW90OyZuYnNwOzxcL3A+XHJcbjxcL2Jsb2NrcXVvdGU+XHJcblxyXG48cD5TdXBwb3NlIHRoYXQgd2UgaGFkIG9ubHkgb25lIGJhbGwuIFdlJiMzOTtkIGhhdmUgdG8gZHJvcCBmcm9tIGVhY2ggZmxvb3IgZnJvbSAxIHRvIDEwMCBpbiBzZXF1ZW5jZSwgcmVxdWlyaW5nIDEwMCBkcm9wcyBpbiB0aGUgd29yc3QgY2FzZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm93IGNvbnNpZGVyIHRoZSBjYXNlIHdoZXJlIHdlIGhhdmUgdHdvIGJhbGxzLiBTdXBwb3NlIHdlIGRyb3AgdGhlIGZpcnN0IGJhbGwgZnJvbSBmbG9vciBuLiBJZiBpdCBicmVha3Mgd2UmIzM5O3JlIGluIHRoZSBjYXNlIHdoZXJlIHdlIGhhdmUgb25lIGJhbGwgcmVtYWluaW5nIGFuZCB3ZSBuZWVkIHRvIGRyb3AgZnJvbSBmbG9vcnMgMSB0byBuLTEgaW4gc2VxdWVuY2UsIHlpZWxkaW5nIG4gZHJvcHMgaW4gdGhlIHdvcnN0IGNhc2UgKHRoZSBmaXJzdCBiYWxsIGlzIGRyb3BwZWQgb25jZSwgdGhlIHNlY29uZCBhdCBtb3N0IG4tMSB0aW1lcykuIEhvd2V2ZXIsIGlmIGl0IGRvZXMgbm90IGJyZWFrIHdoZW4gZHJvcHBlZCBmcm9tIGZsb29yIG4sIHdlIGhhdmUgcmVkdWNlZCB0aGUgcHJvYmxlbSB0byBkcm9wcGluZyBmcm9tIGZsb29ycyBuKzEgdG8gMTAwLiBJbiBlaXRoZXIgY2FzZSB3ZSBtdXN0IGtlZXAgaW4gbWluZCB0aGF0IHdlJiMzOTt2ZSBhbHJlYWR5IHVzZWQgb25lIGRyb3AuIFNvIHRoZSBtaW5pbXVtIG51bWJlciBvZiBkcm9wcywgaW4gdGhlIHdvcnN0IGNhc2UsIGlzIHRoZSBtaW5pbXVtIG92ZXIgYWxsIG4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdSB3aWxsIHdyaXRlIGEgcHJvZ3JhbSB0byBkZXRlcm1pbmUgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGRyb3BzIHJlcXVpcmVkLCBpbiB0aGUgd29yc3QgY2FzZSwgZ2l2ZW4gQiBiYWxscyBhbmQgYW4gTS1zdG9yeSBidWlsZGluZy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgUCwgKDEgJmxlOyBQICZsZTsgMTAwMCksIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgZGF0YSBzZXRzIHRoYXQgZm9sbG93LiBFYWNoIGRhdGEgc2V0IGNvbnNpc3RzIG9mIGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyB0aHJlZSAoMykgZGVjaW1hbCBpbnRlZ2VyIHZhbHVlczogdGhlIHByb2JsZW0gbnVtYmVyLCBmb2xsb3dlZCBieSBhIHNwYWNlLCBmb2xsb3dlZCBieSB0aGUgbnVtYmVyIG9mIGJhbGxzIEIsICgxICZsZTsgQiAmbGU7IDUwKSwgZm9sbG93ZWQgYnkgYSBzcGFjZSBhbmQgdGhlIG51bWJlciBvZiBmbG9vcnMgaW4gdGhlIGJ1aWxkaW5nIE0sICgxICZsZTsgTSAmbGU7IDEwMDApLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGEgc2V0LCBnZW5lcmF0ZSBvbmUgbGluZSBvZiBvdXRwdXQgd2l0aCB0aGUgZm9sbG93aW5nIHZhbHVlczogVGhlIGRhdGEgc2V0IG51bWJlciBhcyBhIGRlY2ltYWwgaW50ZWdlciwgYSBzcGFjZSwgYW5kIHRoZSBtaW5pbXVtIG51bWJlciBvZiBkcm9wcyBuZWVkZWQgZm9yIHRoZSBjb3JyZXNwb25kaW5nIHZhbHVlcyBvZiBCIGFuZCBNLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==