Glass Balls

Interview

Time limit1sMemory limit128 MB

Summary

Given B balls and M floors, compute the minimum number of drops needed to guarantee finding the critical breaking floor in the worst case.

Level: Medium5 of 10
Topics: Dynamic programming, Math, Binary search
Solved: No attempts yet

Problem

You have several glass balls and a building with M floors. Suppose that when a ball is dropped from some floor or any higher floor, it breaks, and from lower floors it does not break. A ball that does not break can be used again; a ball that breaks cannot be used again.

Given B balls, determine the minimum number of drops needed to guarantee that the breaking threshold can be found in the worst case.

Input

The first line contains the number of data sets P. (1 <= P <= 1000)

Each of the next P lines contains one data set. Each line contains two integers B and M, separated by a space: the number of glass balls and the number of floors in the building. (1 <= B <= 50, 1 <= M <= 1000)

Output

For each data set, print one line containing the minimum number of drops that is sufficient in the worst case for B balls and an M-floor building.

Examples1

Example 1
Input
```
4
2 10
2 100
2 300
25 900
```
Expected output
```
4
14
24
10
```