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

문제

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

두 개의 동일한 유리구가 있고, 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
W3sicHJvYmxlbV9pZCI6IjI2OTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZjUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWNlMFx1YzgwNFx1YzgwMVx1Yzc3OCAmIzM5O1x1YjQ1MCBcdWFjMWNcdWM3NTggXHVjNzIwXHViOWFjIFx1YWNmNSYjMzk7IFx1YmIzOFx1YzgxY1x1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0OjxcL3A+XHJcblxyXG48YmxvY2txdW90ZT5cdWI0NTAgXHVhYzFjXHVjNzU4IFx1YjNkOVx1Yzc3Y1x1ZDU1YyBcdWM3MjBcdWI5YWNcdWFkNmNcdWFjMDAgXHVjNzg4XHVhY2UwLCAxMDBcdWNlMzUgXHVjOWRjXHViOWFjIFx1YmU0Y1x1YjUyOVx1YzVkMFx1YzExYyBcdWM3MjBcdWI5YWNcdWFkNmNcdWI5N2MgXHViNWE4XHVjNWI0XHViNzI4XHViODI0XHVjMTFjIFx1YWU2OFx1YzljMFx1YjI5NCBcdWFjMDBcdWM3YTUgXHViMGFlXHVjNzQwIFx1Y2UzNVx1Yzc0NCBcdWNjM2VcdWFjZTAgXHVjMmY2XHViMmU0LiBcdWM3MjBcdWI5YWNcdWFkNmNcdWFjMDAgXHVjNTQ4XHVhZTY4XHVjOWM0XHViMmU0XHViYTc0IFx1YzU0NFx1YmIzNFx1YjdmMCBcdWQ1M2NcdWQ1NzRcdWFjMDAgXHVjNWM2XHViMmU0XHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU1OFx1Yzc5MC4gXHVjNWI0XHViNWJiXHVhYzhjIFx1ZDU3NFx1YzU3YyAoXHVjZDVjXHVjNTQ1XHVjNzU4IFx1YzBjMVx1ZDY2OVx1YzVkMFx1YzExY1x1YjNjNCkgXHVhYzAwXHVjN2E1IFx1YmU2OFx1YjlhYyBcdWNjM2VcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz88XC9ibG9ja3F1b3RlPlxyXG5cclxuPHA+XHVjNmIwXHViOWFjXHVhYzAwIFx1YzYyNFx1YzljMSBcdWQ1NThcdWIwOThcdWM3NTggXHVhY2Y1XHVjNzc0IFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NThcdWM3OTAuIFx1YWRmOFx1YjdlY1x1YmE3NCBcdWM2YjBcdWI5YWNcdWIyOTQgMVx1Y2UzNVx1YmQ4MFx1ZDEzMCAxMDBcdWNlMzVcdWFlNGNcdWM5YzAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YjVhOFx1YzViNFx1YjcyOFx1YjgyNFx1YmNmNFx1YjI5NCBcdWJjMjlcdWJjOTUgXHViYzE2XHVjNWQwIFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZDVjXHVjNTQ1XHVjNzU4IFx1YWNiZFx1YzZiMFx1YjI5NCAxMDBcdWJjODhcdWI5Y2NcdWM1ZDAgXHVjYzNlXHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjODFjIFx1YzZiMFx1YjlhY1x1YzVkMFx1YWM4YyBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YWNmNVx1Yzc3NCBcdWM3ODhcdWIyZTRcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWFjZjVcdWM3NDQgblx1Y2UzNVx1YzVkMFx1YzExYyBcdWI1YThcdWM1YjRcdWI3MjhcdWI5YjBcdWIyZTRcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWI5Y2NcdWM1N2RcdWM1ZDAgXHVhZGY4XHVhYzhjIFx1YWU2OFx1YzljNFx1YjJlNFx1YmE3NCBcdWIyZTRcdWMyZGMgXHVhY2Y1IFx1ZDU1OFx1YjA5OFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViODVjIFx1YjNjY1x1YzU0NFx1YWMwMFx1YzExYywgMVx1Y2UzNVx1YmQ4MFx1ZDEzMCBuLTFcdWNlMzVcdWFlNGNcdWM5YzAgXHVjMmRjXHViM2M0XHVkNTc0XHViY2Y0XHViYTc0XHViNDFjXHViMmU0LiBcdWM3NzQgXHVhY2JkXHVjNmIwIFx1Y2Q1Y1x1YzU0NVx1Yzc1OCBcdWFjYmRcdWM2YjAgMSsobi0xKSwgXHVjOTg5IG5cdWJjODhcdWM3NTggXHVjMmRjXHViM2M0XHViOWNjXHVjNWQwIFx1Y2MzZVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2Mgblx1Y2UzNVx1YzVkMFx1YzExYyBcdWFlNjhcdWM5YzBcdWM5YzAgXHVjNTRhXHVjNTU4XHViMmU0XHViYTc0LCBuKzFcdWNlMzVcdWM1ZDBcdWMxMWMgMTAwXHVjZTM1XHVhZTRjXHVjOWMwXHViOWNjIFx1YzJlNFx1ZDVkOFx1ZDU3NFx1YmNmNFx1YmE3NCBcdWI0MWNcdWIyZTQuIFx1YWU2OFx1YzljMFx1YWM3MFx1YjA5OCBcdWFlNjhcdWM5YzBcdWM5YzAgXHVjNTRhXHVjNTU4XHVhYzcwXHViMDk4IFx1YzZiMFx1YjlhY1x1YjI5NCBcdWQ1NWMgXHViYzg4XHVjNzU4IFx1YzJkY1x1YjNjNFx1Yjk3YyBcdWQ1NThcdWM2MDBcdWIyZTQuIFx1YWRmOFx1Yjc5OFx1YzExYyZuYnNwO1x1YmFhOFx1YjRlMCBuXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NzQgXHVjZDVjXHVjNTQ1XHVjNzU4IFx1YWNiZFx1YzZiMCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjMmU0XHVkNWQ4IFx1ZDY5Zlx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+Qlx1YWMxY1x1Yzc1OCBcdWFjZjVcdWFjZmMgTVx1Y2UzNSBcdWM5ZGNcdWI5YWMgXHViZTRjXHViNTI5XHVjNWQwXHVjMTFjIFx1Y2Q1Y1x1YzU0NVx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHViYTg3IFx1YmM4OCBcdWFjZjVcdWM3NDQgXHViNWE4XHVjNWI0XHViNzI4XHViODI0XHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM3NDAgXHViMzcwXHVjNzc0XHVkMTMwIFx1YzEzOFx1ZDJiOCBcdWMyMTggUCgxICZsZTsgUCAmbGU7IDEwMDApXHVhYzAwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWIzNzBcdWM3NzRcdWQxMzAgXHVjMTM4XHVkMmI4XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0IFx1Yzc4OFx1YzczY1x1YmE3MCAyXHVhYzFjXHVjNzU4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjNzIwXHViOWFjXHVhY2Y1XHVjNzU4IFx1YWMxY1x1YzIxOCBCKDEgJmxlOyBCICZsZTsgNTApLCBcdWFjNzRcdWJiM2NcdWM3NTggXHVjZTM1IFx1YzIxOCBNKDEgJmxlOyBNICZsZTsgMTAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHViMzcwXHVjNzc0XHVkMTMwIFx1YzEzOFx1ZDJiOFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVkNTVjIFx1YzkwNCBcdWM1MjksIEIsIE1cdWM1ZDAgXHViMzAwXHVkNTc0IChcdWNkNWNcdWM1NDVcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwXHViM2M0KVx1YWMwMFx1YzdhNSBcdWM4MDFcdWM3NDAgXHVkNjlmXHVjMjE4XHVjNzU4IFx1YzJkY1x1YjNjNCBcdWQ2OWZcdWMyMThcdWI5N2MgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzVlYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjY5NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJhbGxzIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgY2xhc3NpYyBUd28gR2xhc3MgQmFsbHMgYnJhaW4tdGVhc2VyIGlzIG9mdGVuIHBvc2VkIGFzOiZuYnNwOzxcL3A+XHJcblxyXG48YmxvY2txdW90ZT5cclxuPHA+JnF1b3Q7R2l2ZW4gdHdvIGlkZW50aWNhbCBnbGFzcyBzcGhlcmVzLCB5b3Ugd291bGQgbGlrZSB0byBkZXRlcm1pbmUgdGhlIGxvd2VzdCBmbG9vciBpbiBhIDEwMC1zdG9yeSBidWlsZGluZyBmcm9tIHdoaWNoIHRoZXkgd2lsbCBicmVhayB3aGVuIGRyb3BwZWQuIEFzc3VtZSB0aGUgc3BoZXJlcyBhcmUgdW5kYW1hZ2VkIHdoZW4gZHJvcHBlZCBiZWxvdyB0aGlzIHBvaW50LiBXaGF0IGlzIHRoZSBzdHJhdGVneSB0aGF0IHdpbGwgbWluaW1pemUgdGhlIHdvcnN0LWNhc2Ugc2NlbmFyaW8gZm9yIG51bWJlciBvZiBkcm9wcz8mcXVvdDsmbmJzcDs8XC9wPlxyXG48XC9ibG9ja3F1b3RlPlxyXG5cclxuPHA+U3VwcG9zZSB0aGF0IHdlIGhhZCBvbmx5IG9uZSBiYWxsLiBXZSYjMzk7ZCBoYXZlIHRvIGRyb3AgZnJvbSBlYWNoIGZsb29yIGZyb20gMSB0byAxMDAgaW4gc2VxdWVuY2UsIHJlcXVpcmluZyAxMDAgZHJvcHMgaW4gdGhlIHdvcnN0IGNhc2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vdyBjb25zaWRlciB0aGUgY2FzZSB3aGVyZSB3ZSBoYXZlIHR3byBiYWxscy4gU3VwcG9zZSB3ZSBkcm9wIHRoZSBmaXJzdCBiYWxsIGZyb20gZmxvb3Igbi4gSWYgaXQgYnJlYWtzIHdlJiMzOTtyZSBpbiB0aGUgY2FzZSB3aGVyZSB3ZSBoYXZlIG9uZSBiYWxsIHJlbWFpbmluZyBhbmQgd2UgbmVlZCB0byBkcm9wIGZyb20gZmxvb3JzIDEgdG8gbi0xIGluIHNlcXVlbmNlLCB5aWVsZGluZyBuIGRyb3BzIGluIHRoZSB3b3JzdCBjYXNlICh0aGUgZmlyc3QgYmFsbCBpcyBkcm9wcGVkIG9uY2UsIHRoZSBzZWNvbmQgYXQgbW9zdCBuLTEgdGltZXMpLiBIb3dldmVyLCBpZiBpdCBkb2VzIG5vdCBicmVhayB3aGVuIGRyb3BwZWQgZnJvbSBmbG9vciBuLCB3ZSBoYXZlIHJlZHVjZWQgdGhlIHByb2JsZW0gdG8gZHJvcHBpbmcgZnJvbSBmbG9vcnMgbisxIHRvIDEwMC4gSW4gZWl0aGVyIGNhc2Ugd2UgbXVzdCBrZWVwIGluIG1pbmQgdGhhdCB3ZSYjMzk7dmUgYWxyZWFkeSB1c2VkIG9uZSBkcm9wLiBTbyB0aGUgbWluaW11bSBudW1iZXIgb2YgZHJvcHMsIGluIHRoZSB3b3JzdCBjYXNlLCBpcyB0aGUgbWluaW11bSBvdmVyIGFsbCBuLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3Ugd2lsbCB3cml0ZSBhIHByb2dyYW0gdG8gZGV0ZXJtaW5lIHRoZSBtaW5pbXVtIG51bWJlciBvZiBkcm9wcyByZXF1aXJlZCwgaW4gdGhlIHdvcnN0IGNhc2UsIGdpdmVuIEIgYmFsbHMgYW5kIGFuIE0tc3RvcnkgYnVpbGRpbmcuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIFAsICgxICZsZTsgUCAmbGU7IDEwMDApLCB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGRhdGEgc2V0cyB0aGF0IGZvbGxvdy4gRWFjaCBkYXRhIHNldCBjb25zaXN0cyBvZiBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgdHdvICgyKSBkZWNpbWFsIGludGVnZXIgdmFsdWVzOiB0aGUgbnVtYmVyIG9mIGJhbGxzIEIsICgxICZsZTsgQiAmbGU7IDUwKSwgZm9sbG93ZWQgYnkgYSBzcGFjZSBhbmQgdGhlIG51bWJlciBvZiBmbG9vcnMgaW4gdGhlIGJ1aWxkaW5nIE0sICgxICZsZTsgTSAmbGU7IDEwMDApLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGEgc2V0LCBnZW5lcmF0ZSBvbmUgbGluZSBvZiBvdXRwdXQgd2l0aCB0aGUgZm9sbG93aW5nIHZhbHVlOiBUaGUgbWluaW11bSBudW1iZXIgb2YgZHJvcHMgbmVlZGVkIGZvciB0aGUgY29ycmVzcG9uZGluZyB2YWx1ZXMgb2YgQiBhbmQgTS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d