У графа Михаила есть $n$ усадеб расположенных по кругу. Он хочет построить несколько подземных переходов между усадьбами, чтобы перемещаться между ними быстрее. Вы можете выбрать какое-то число $k$, такое, что для каждой усадьбы она будет соединена с соседними $k$ усадьбами слева и $k$ усадьбами справа. Какое же минимальное $k$ вы должны выбрать, чтобы кратчайшее расстояние между любыми двумя усадьбами было не больше $d$? Расстояние между двумя усадьбами измерятеся в количестве переходов, которые нужно сделать, чтобы добраться из одной усадьбы в другую.

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

Первая строка содержит одно целое число $t$ ($1 ⩽ t ⩽ 10$) — число наборов входных данных. Для каждого набора входных данных на новой строке вводится два целых числа $n$ и $d$ ($3 ⩽ n ⩽ 10^{12}$, $1 ⩽ d ⩽ 10^{12}$).

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

Для каждого набора входных данных выведите одно число - минимальное $k$ удовлетворяющее условию. Числа разделяйте переводами строк.

Система оценки

В задаче 20 тестов, за каждый из которых вы получите 5 баллов.

Решения, корректно работающие при $n, d ⩽ 10^4$ получат не менее 25 баллов.

Решения, корректно работающие при $n, d ⩽ 10^9$ получат не менее 70 баллов.