Electrician

There are $n$ houses with internet access in village J. One of them is home to a villain who keeps posting angry comments about us on social media from a fake account. We do not know which house it is, and we want to find out.

The electrical substation has $n$ switches, one for each house. When a switch is on, its house has light and internet access. When it is off, the house has no light and no internet. At the start, every switch is on. At the start of each hour, we can set the switches in any pattern we like, turning some on and some off. Then, during the following hour, we watch social media: if the villain's house has light, comments appear for sure, and if not, none appear. When the investigation ends, we must turn every light back on.

If the light in the villain's house goes out more than $k$ times, the villain becomes suspicious, and we want to avoid that. A light may stay off for a long time without cost. Only the number of times it is switched off counts. What is the minimum number of hours needed to identify the villain's house with certainty and restore the light in every house?

The first line contains an integer $t$, the number of test cases ($1 \le t \le 2 \cdot 10^5$). Each of the next $t$ lines contains two integers $n$ and $k$: the number of houses, and the maximum number of times we can switch the light off in the villain's house ($1 \leq n, k \leq 10^{18}$).

For each test case, print on one line the minimum number of hours needed to identify the villain's house and restore the light in every house.

In the first test case, $n = 3$ and $k = 1$. In the first hour, turn off the lights in houses 1 and 2. After an hour, turn the light back on in house 1, and after another hour, turn it back on in house 2. At the beginning of the third hour, we know for sure where the villain lives, and we restore the light in all houses.