Настройки поиска

Условие:
Банда из k зайцев совершила разбойный налёт на склад с капустой и похитила n кочанов. Лиса в это время пробегала мимо и предложила им поделить награбленную капусту поровну между всеми членами банды. Зайцы согласились, условившись с лисой, что всем зайцам достанется одинаковое количество кочанов капусты, а остаток размером менее k кочанов лиса сможет забрать себе как плату за эту услугу.
Между тем, при разделе капусты к банде присоединился один заяц, который не принимал участия в налёте. Он получил ровно такую же долю, как и члены банды, однако остался незамеченным. «Почему?» — спросите вы. Дело в том, что каждый заяц получил такое же количество кочанов капусты, какое получил бы, если бы самозванец при разделе не присутствовал. Найдите минимальное количество зайцев в банде, при котором такое могло произойти.
Исходные данные:
Входные данные состоят из нескольких тестов. Первая строка содержит количество тестов t, 1 ? t ? 30000. В каждой из следующих t строк записано целое число n, 1 ? n ? 10^18.
Результат:
Для каждого теста выведите в отдельной строке целое число k — минимально возможное количество зайцев в банде.

Уже достаточно давно думаю над этой задачей. Мат. модель очевидна, нужно найти такое k, что n / k = n / (k + 1). Подключил всю команду, никаких результатов. Где-то слышал, что существует формула, от которой достаточно пройтись в две стороны на небольшое количество шагов. Где-то слышал, что надо что-то колдовать с функцией F(x) = [n/x] - [n/(x + 1)]. Но ни одну из идей развить не удалось.
На каком-то из форумов видел сообщение e-maxx'a о решении какого-то псевдоквадратного уравнения, но и это мне, конечно же, не помогло.
P.S. Если идти от корня и тупо проверять, то решение очевидно получит TLE, ведь при больших N количество шагов будет порядка нескольких десятков тысяч.