문제
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)를 계산하는 프로그램을 작성하시오.
입력
입력파일은 INPUT.TXT로 한다.
입력의 첫 줄에는 테스트 케이스의 개수 T(1≤T≤10)가 주어진다.
각 테스트 케이스는 한 줄에 빌딩 전체의 층 수와 금고의 개수를 의미하는 두 개의 정수 N과 K(1≤K≤N≤500)가 순서대로 주어진다.
출력
출력파일은 OUTPUT.TXT로 한다.
각 테스트 케이스에 대해서 E(N K)를 한 줄에 하나씩 출력하시오.
예제
3
5 1
4 2
8 3
5
3
4
로그인해야 코드를 작성할 수 있어요.