B. Приключения Алисы в перестановках
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса перепутала слова трансмутация и перестановка! У неё есть массив $$$a$$$, заданный тремя целыми числами $$$n$$$, $$$b$$$, $$$c$$$: массив $$$a$$$ имеет длину $$$n$$$ и задаётся по правилу $$$a_i = b\cdot (i - 1) + c$$$ для $$$1\le i\le n$$$. Например, если $$$n=3$$$, $$$b=2$$$ и $$$c=1$$$, то $$$a=[2 \cdot 0 + 1, 2 \cdot 1 + 1, 2 \cdot 2 + 1] = [1, 3, 5]$$$.

Алисе очень нравятся перестановки $$$[0, \ldots, n-1]$$$$$$^{\text{∗}}$$$ и она хотела бы преобразовать $$$a$$$ в перестановку. В одной операции Алиса заменяет максимальный элемент массива $$$a$$$ на $$$\operatorname{MEX}$$$$$$^{\text{†}}$$$ массива $$$a$$$. Если в массиве $$$a$$$ несколько максимальных элементов, Алиса выбирает самый левый для замены.

Можете ли вы помочь Алисе выяснить, сколько операций ей нужно выполнить, чтобы $$$a$$$ впервые стал перестановкой? Если это невозможно, вы должны сообщить об этом.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$0$$$ до $$$n-1$$$ в произвольном порядке. Обратите внимание, это немного отличается от обычного определения перестановки. Например, $$$[1,2,0,4,3]$$$ — перестановка, но $$$[0,1,1]$$$ не перестановка ($$$1$$$ встречается в массиве дважды) и $$$[0,2,3]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$3$$$).

$$$^{\text{†}}$$$$$$\operatorname{MEX}$$$ массива — это наименьшее неотрицательное целое число, которое не принадлежит массиву. Например, $$$\operatorname{MEX}$$$ массива $$$[0, 3, 1, 3]$$$ равно $$$2$$$, а $$$\operatorname{MEX}$$$ массива $$$[5]$$$ равно $$$0$$$.

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

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

Единственная строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$b$$$, $$$c$$$ ($$$1\le n\le 10^{18}$$$; $$$0\le b$$$, $$$c\le 10^{18}$$$) — параметры массива.

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

Для каждого набора входных данных, если массив никогда не сможет стать перестановкой, выведите одно целое число $$$-1$$$. В противном случае выведите минимальное количество операций, необходимых для того, чтобы массив стал перестановкой.

Пример
Входные данные
7
10 1 0
1 2 3
100 2 1
3 0 1
3 0 0
1000000000000000000 0 0
1000000000000000000 1000000000000000000 1000000000000000000
Выходные данные
0
1
50
2
-1
-1
1000000000000000000
Примечание

В первом наборе входных данных массив уже $$$[0, 1, \ldots, 9]$$$, поэтому операции не требуются.

В третьем наборе входных данных начальный массив равен $$$[1, 3, 5, \ldots, 199]$$$. После первой операции $$$199$$$ преобразуется в $$$0$$$. Во второй операции $$$197$$$ преобразуется в $$$2$$$. Если продолжать, потребуется ровно $$$50$$$ операций, чтобы получить массив $$$[0, 1, 2, 3, \ldots, 99]$$$.

В четвертом наборе входных данных требуется две операции: $$$[1,1,1] \to [0,1,1] \to [0,2,1]$$$.

В пятом наборе входных данных процесс выглядит следующим образом: $$$[0,0,0] \to [1,0,0] \to [2,0,0] \to [1,0,0] \to [2,0,0]$$$. Этот процесс повторяется бесконечно, поэтому массив никогда не становится перестановкой, и ответ равен $$$-1$$$.