D. K-хорошие
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мы говорим, что натуральное число $$$n$$$ является $$$k$$$-хорошим для некоторого положительного целого числа $$$k$$$, если $$$n$$$ можно представить в виде суммы $$$k$$$ целых положительных чисел, которые дают $$$k$$$ различных остатков при делении на $$$k$$$.

По заданному натуральному числу $$$n$$$ найдите такое $$$k \geq 2$$$, что $$$n$$$ является $$$k$$$-хорошим, или скажите, что такого $$$k$$$ не существует.

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

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

Каждый набор входных данных состоит из одной строки с целым числом $$$n$$$ ($$$2 \leq n \leq 10^{18}$$$).

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

Для каждого набора входных данных выведите строку со значением $$$k$$$ таким, что $$$n$$$ является $$$k$$$-хорошим ($$$k \geq 2$$$), или $$$-1$$$, если $$$n$$$ не является $$$k$$$-хорошим для любых $$$k$$$. Если существует несколько допустимых значений $$$k$$$, вы можете вывести любое из них.

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

$$$6$$$ является $$$3$$$-хорошим числом, поскольку его можно представить в виде суммы $$$3$$$ чисел, которые дают разные остатки при делении на $$$3$$$: $$$6 = 1 + 2 + 3$$$.

$$$15$$$ также является $$$3$$$-хорошим числом, поскольку $$$15 = 1 + 5 + 9$$$, а $$$1, 5, 9$$$ дают разные остатки при делении на $$$3$$$.

$$$20$$$ — это $$$5$$$-хорошее число, поскольку $$$20 = 2 + 3 + 4 + 5 + 6$$$ и $$$2,3,4,5,6$$$ дают разные остатки при делении на $$$5$$$.