Allergen Testing

You are in a chemistry class, and you are working with some compounds, exactly one of which you are allergic to. You have a fixed number of days to figure out which compound it is. You set up a number of sites on your arm for testing. On each day, you do the following exactly once:

1. Apply each compound to some (possibly empty) subset of sites on your arm. You can apply more than one compound to the same site.
2. Wait and see which sites demonstrate an allergic reaction.

A site demonstrates an allergic reaction if and only if the compound you are allergic to is applied to that site. If a site demonstrates an allergic reaction, it cannot be used on future days.

Compute the minimum number of sites you'll need on your arm to guarantee that you can determine exactly which compound you are allergic to within the given number of days.

The first line of input contains a single integer $t$ ($1 \le t \le 10^4$), which is the number of test cases that follow.

Each of the next $t$ lines contains two integers $n$ and $d$ ($1 \le n,d \le 10^{18}$) describing a test case, where $n$ is the number of compounds and $d$ is the number of days.

Output $t$ lines. On each line output a single integer, which is the minimum number of sites on your arm necessary to discover which of the $n$ compounds is the allergen within $d$ days for that test case. Output the answers to the test cases in the order they appear in the input.