A. Сколько квадратов?
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Льюиса была последовательность из $$$n+1$$$ целого числа $$$a_1, a_2, \ldots, a_{n+1}$$$. Для каждого $$$i = 1, 2, \ldots, n+1$$$ известно, что или $$$0\leq a_i < n$$$, или $$$a_i=n^2$$$. Льюис вычислил сумму всех элементов последовательности и обозначил ее за $$$s$$$.

Льюис потерял последовательность, но он помнит значения $$$n$$$ и $$$s$$$. Можете определить, сколько элементов последовательности были равны $$$n^2$$$?

Можно показать, что при данных ограничениях ответ всегда существует и единственный.

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

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 2\cdot 10^4$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

Единственная строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$s$$$ ($$$1\le n< 10^6$$$, $$$0\le s \le 10^{18}$$$). Гарантируется, что значение $$$s$$$ является суммой чисел некоторой последовательности, удовлетворяющей описанным ограничениям.

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

Для каждого набора входных данных выведите одно целое число — количество элементов последовательности, равных $$$n^2$$$.

Пример
Входные данные
4
7 0
1 1
2 12
3 12
Выходные данные
0
1
3
1
Примечание

В первом наборе входных данных $$$s=0$$$, поэтому все числа должны быть равны $$$0$$$, и нет ни одного числа, равного $$$49$$$.

Во втором наборе $$$s=1$$$. Существуют две подходящие последовательности: $$$[0, 1]$$$ и $$$[1, 0]$$$. В обоих случаях число $$$1$$$ встречается один раз.

В третьем наборе $$$s=12$$$, что в данном случае является максимально возможным значением $$$s$$$. Поэтому число $$$4$$$ встречается $$$3$$$ раза в последовательности.