Круглый Граф

Сложность: 15%

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

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

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

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

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

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

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

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

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

STDINSTDOUT
2
6 2
3 1
2
1

Примечание

В первом наборе входных данных если мы соединим каждую усадьбу с каждым из соседей (т.е. если k=1k = 1), то для попадания в противоположную усадьбу нужно будет совершить 3 перехода (см. рисунок) Если соединить каждую усадьбу с двумя соседями (k=2k = 2) будет ситуация как на рисунке и потребуется не больше двух переходов для попадания из любой усадьбы в любую. Во втором наборе данных мы просто соединяем все усадьбы (k=1k = 1).