시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 83 42 37 60.656%

문제

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

두 개의 동일한 유리구가 있고, 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에 대해 (최악의 경우에도)가장 적은 횟수의 시도 횟수를 공백으로 구분하여 출력한다.

예제 입력

4
2 10
2 100
2 300
25 900

예제 출력

4
14
24
10

힌트