금고

N층 빌딩이 있다. 이 빌딩의 F층은 금고를 떨어뜨렸을때에 부서지는 최소층이다. 다시 말하면, F층을 포함하여 그위의 층에서 금고를 떨어뜨리면 무조건 부서지며, F층의 아래층에서 금고를 떨어뜨릴 떄에는 금고는 절대 부서지지 않는다.(N층에서도 부서지지 않으며, 1층에서도 부서질수도 있다.)

새로 개발한 금고의 견고함을 측정해서 광고하려고 하는데, 금고 K개를 가지고 이 빌딩의 F층이 몇 층인지를 알고 싶다. 가능한 방법은 임의의 층에서 직접 금고를 떨어뜨리고 그 결과를 확인 하는 것 뿐이다. 물론, 부서진 금고는 다시 사용할수 없으며 부서지지 않았다면 다시 사용할수 있다.

이런상황에서 K개의 금고를 가지고 F층이 몇층이던 간에 F층을 알아낼수 있는 최소한의 금고 낙하 획수를 E(N,K)이라 하자. 예를 들어 K = 1이라면 F를 알아내기 전에 금고가 부서지면 안되기 때문에 1층부터 차례대로 올라가면서 금고를 낙하해야 하며 많아야 N번이면 F층을 알아 낼수 있다. 따라서 E(N, 1) = N이다. 건물의 층수를 나타내는 정수 N과 금고의 개수를 나타내는 정수 k가 주어 졌을때, E(N,K)를 계산하는 프로그램을 작성하시오.

입력은 표준 입력(standard input)을 통해 받아들인다. 입력의 첫줄에는 테스트 케이스의 개수 T(1 <= T <= 10)가 주어진다. 각 테스트 케이스는 한줄에 빌딩 전체 층수와 금고의 개수를 의미하는 두개의 정수 N과 K(1 <= K <= N <= 500)가 순서대로 주어진다.

출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대해서 E(N, K)를 한줄에 하나씩 출력하시오.

3
5 1
4 2
8 3

5
3
4

10
4 2
382 5
500 1
500 3
496 2
500 500
481 4
255 7
255 8
256 9

3
10
500
15
31
9
11
9
8
9

----
문제분류 경시대회준비반