Электрик
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мебибайт
ввод
стандартный ввод
вывод
стандартный вывод

В деревне J есть $$$n$$$ домов с доступом в интернет. В одном из домов сидит злодей и делает свои злодейские дела: пишет нам без остановки гневные комментарии в соцсетях с фейкового аккаунта. Мы не знаем, в каком доме он живёт, но хотим это выяснить.

На электроподстанции есть $$$n$$$ рубильников: по одному для каждого дома. Когда рубильник включён, свет в доме есть, а когда выключен — нет, а значит, нет и доступа в интернет. Изначально все рубильники включены. В начале каждого часа мы можем произвольно менять состояние рубильников: какие-то включать, какие-то выключать. После чего в течение следующего часа мы следим за соцсетями: если в доме злодея есть свет, комментарии обязательно появятся, а если света нет, то и комментариев не будет. После наших исследований мы должны вернуть всё в исходное состояние: включить свет во всех домах.

К сожалению, если свет в доме злодея пропадёт более $$$k$$$ раз, то он заподозрит неладное, а мы хотели бы этого избежать. При этом, когда свет просто долго отсутствует, это не вызывает подозрения — учитывается именно число отключений. За какое наименьшее число часов мы можем с уверенностью сказать, в каком доме живёт злодей, и включить всем свет?

Входные данные

В первой строке задано целое число $$$t$$$ — число наборов входных данных ($$$1 \le t \leq 2 \cdot 10^5$$$). Далее следуют $$$t$$$ наборов.

Каждый набор входных данных задан на отдельной строке, содержащей два целых числа $$$n$$$ и $$$k$$$ — число домов и максимальное возможное число отключений света в доме злодея ($$$1 \leq n, k \leq 10^{18}$$$).

Выходные данные

Для каждого набора входных данных выведите строку с одним целым числом: наименьшим числом часов, которые потребуются, чтобы точно определить дом злодея и включить всем свет.

Пример

Входные данные
5
3 1
4 1
2 2
17 3
73 6
Выходные данные
2
2
1
5
7

Примечание

В первом наборе входных данных $$$n = 3$$$ и $$$k = 1$$$. Мы можем в начале первого часа отключить свет в домах с номерами $$$1$$$ и $$$2$$$, затем спустя час вернуть свет в доме номер $$$1$$$, а спустя ещё час — вернуть свет в доме номер $$$2$$$. К началу третьего часа мы будем точно знать, где живёт злодей, и вернём свет во все дома.