D. Марафон решения задач
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп решил устроить себе марафон решения задач. Он хочет решить $$$s$$$ задач за $$$n$$$ дней. Пусть $$$a_i$$$ будет количеством задач, которые он решит в $$$i$$$-й день. Он хочет найти такое разбиение задач на дни, что:

  • $$$a_i$$$ — это целое число для всех $$$i$$$ от $$$1$$$ до $$$n$$$;
  • $$$a_i \ge 1$$$ для всех $$$i$$$ от $$$1$$$ до $$$n$$$;
  • $$$a_{i + 1} \ge a_i$$$ для всех $$$i$$$ от $$$1$$$ до $$$n-1$$$;
  • $$$a_{i + 1} \le 2 \cdot a_i$$$ для всех $$$i$$$ от $$$1$$$ до $$$n-1$$$;
  • $$$a_n$$$ как можно больше.

Обратите внимание, что $$$a_1$$$ может быть произвольно большим.

Какое наибольшее значение $$$a_n$$$ Поликарп может получить?

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

Затем следуют описания $$$t$$$ наборов входных данных.

В единственной строке каждого набора входных данных записаны два целых числа $$$n$$$ и $$$s$$$ ($$$1 \le n \le s \le 10^{18}$$$) — количество дней и количество задач, которые Поликарп хочет решить.

Гарантируется, что разбиение всегда существует в данных ограничениях.

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

На каждый набор входных данных выведите одно целое число — наибольшее значение $$$a_n$$$.

Пример
Входные данные
3
1 15
3 9
2 6
Выходные данные
15
4
4
Примечание

В первом наборе входных данных есть только одно разбиение: $$$[15]$$$.

Во втором примере разбиение, которое максимизирует $$$a_n$$$: $$$[2, 3, 4]$$$.

В третьем примере разбиение, которое максимизирует $$$a_n$$$: $$$[2, 4]$$$. $$$[3, 3]$$$ является корректным разбиением, но $$$a_n=3$$$, что меньше $$$4$$$. $$$[1, 5]$$$ не является корректным разбиением, потому что $$$5 > 2 \cdot 1$$$.