B. Наибольший интервал делителей
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано число $$$n$$$. Найдите максимальный размер интервала $$$[l, r]$$$ из целых положительных чисел такого, что для каждого числа $$$i$$$ из этого интервала (т.е. $$$l \leq i \leq r$$$) $$$n$$$ кратно $$$i$$$.

Если вам даны два целых числа $$$l\le r$$$, то размер интервала $$$[l, r]$$$ равен $$$r-l+1$$$ (т.е. совпадает с количеством целых чисел, принадлежащих интервалу).

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

Первая строка содержит единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Единственная строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^{18}$$$).

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

Для каждого набора входных данных вывести одно целое число: максимальный размер допустимого интервала.

Пример
Входные данные
10
1
40
990990
4204474560
169958913706572972
365988220345828080
387701719537826430
620196883578129853
864802341280805662
1000000000000000000
Выходные данные
1
2
3
6
4
22
3
1
2
2
Примечание

В первом наборе входных данных допустимым интервалом с максимальным размером является $$$[1, 1]$$$ (он допустим, так как $$$n = 1$$$ кратно $$$1$$$) и его размер равен $$$1$$$.

Во втором наборе входных данных допустимым интервалом с максимальным размером является $$$[4, 5]$$$ (он допустим, так как $$$n = 40$$$ кратно $$$4$$$ и $$$5$$$), а его размер равен $$$2$$$.

В третьем наборе входных данных допустимым интервалом с максимальным размером является $$$[9, 11]$$$.

В четвертом наборе входных данных допустимым интервалом с максимальным размером является $$$[8, 13]$$$.

В седьмом наборе входных данных допустимым интервалом с максимальным размером является $$$[327869, 327871]$$$.