В деревне J есть $$$n$$$ домов с доступом в интернет. В одном из домов сидит злодей и делает свои злодейские дела: пишет нам без остановки гневные комментарии в соцсетях с фейкового аккаунта. Мы не знаем, в каком доме он живёт, но хотим это выяснить.
На электроподстанции есть $$$n$$$ рубильников: по одному для каждого дома. Когда рубильник включён, свет в доме есть, а когда выключен — нет, а значит, нет и доступа в интернет. Изначально все рубильники включены. В начале каждого часа мы можем произвольно менять состояние рубильников: какие-то включать, какие-то выключать. После чего в течение следующего часа мы следим за соцсетями: если в доме злодея есть свет, комментарии обязательно появятся, а если света нет, то и комментариев не будет. После наших исследований мы должны вернуть всё в исходное состояние: включить свет во всех домах.
К сожалению, если свет в доме злодея пропадёт более $$$k$$$ раз, то он заподозрит неладное, а мы хотели бы этого избежать. При этом, когда свет просто долго отсутствует, это не вызывает подозрения — учитывается именно число отключений. За какое наименьшее число часов мы можем с уверенностью сказать, в каком доме живёт злодей, и включить всем свет?
В первой строке задано целое число $$$t$$$ — число наборов входных данных ($$$1 \le t \leq 2 \cdot 10^5$$$). Далее следуют $$$t$$$ наборов.
Каждый набор входных данных задан на отдельной строке, содержащей два целых числа $$$n$$$ и $$$k$$$ — число домов и максимальное возможное число отключений света в доме злодея ($$$1 \leq n, k \leq 10^{18}$$$).
Для каждого набора входных данных выведите строку с одним целым числом: наименьшим числом часов, которые потребуются, чтобы точно определить дом злодея и включить всем свет.
53 14 12 217 373 6
2 2 1 5 7
В первом наборе входных данных $$$n = 3$$$ и $$$k = 1$$$. Мы можем в начале первого часа отключить свет в домах с номерами $$$1$$$ и $$$2$$$, затем спустя час вернуть свет в доме номер $$$1$$$, а спустя ещё час — вернуть свет в доме номер $$$2$$$. К началу третьего часа мы будем точно знать, где живёт злодей, и вернём свет во все дома.