У графа Михаила есть $$$n$$$ усадеб расположенных по кругу. Он хочет построить несколько подземных переходов между усадьбами, чтобы перемещаться между ними быстрее. Вы можете выбрать какое-то число $$$k$$$, такое, что для каждой усадьбы она будет соединена с соседними $$$k$$$ усадьбами слева и $$$k$$$ усадьбами справа. Какое же минимальное $$$k$$$ вы должны выбрать, чтобы кратчайшее расстояние между любыми двумя усадьбами было не больше $$$d$$$? Расстояние между двумя усадьбами измерятеся в количестве переходов, которые нужно сделать, чтобы добраться из одной усадьбы в другую.
Первая строка содержит одно целое число $$$t$$$ $$$(1 \le t \le 10)$$$ — число наборов входных данных.
Для каждого набора входных данных на новой строке вводится два целых числа $$$n$$$ и $$$d$$$ $$$(3 \le n \le 10^{12}, 1 \le d \le 10^{12})$$$.
Для каждого набора входных данных выведите одно число — минимальное $$$k$$$ удовлетворяющее условию. Числа разделяйте переводами строк или пробелами.
Решения, корректно работающие при $$$n, d \le 10^4$$$ получат не менее 25% баллов.
Решения, корректно работающие при $$$n, d \le 10^9$$$ получат не менее 70% баллов.
2 6 2 3 1
2 1
В первом наборе входных данных если мы соединим каждую усадьбу с каждым из соседей (т.е. если $$$k$$$ = 1), то для попадания в противоположную усадьбу нужно будет совершить 3 перехода (см. рисунок)
Если соединить каждую усадьбу с двумя соседями ($$$k$$$ = 2) будет ситуация как на рисунке и потребуется не больше двух переходов для попадания из любой усадьбы в любую.
Во втором наборе данных мы просто соединяем все усадьбы ($$$k$$$ = 1).
