#1168 금고

12  2 s   128 MB  

Description

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

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

 

 

Output

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

 

 

Sample Input

Sample Output

3
5 1
4 2
8 3
5
3
4