Банда из k зайцев совершила разбойный налёт на склад с капустой и похитила n кочанов. Лиса в это время пробегала мимо и предложила им поделить награбленную капусту поровну между всеми членами банды. Зайцы согласились, условившись с лисой, что всем зайцам достанется одинаковое количество кочанов капусты, а остаток размером менее k кочанов лиса сможет забрать себе как плату за эту услугу.

Между тем, при разделе капусты к банде присоединился один заяц, который не принимал участия в налёте. Он получил ровно такую же долю, как и члены банды, однако остался незамеченным. «Почему?» — спросите вы. Дело в том, что каждый заяц получил такое же количество кочанов капусты, какое получил бы, если бы самозванец при разделе не присутствовал. Найдите минимальное количество зайцев в банде, при котором такое могло произойти.

Входные данные состоят из нескольких тестов. Первая строка содержит количество тестов t, 1 ≤ t ≤ 30000. В каждой из следующих t строк записано целое число n, 1 ≤ n ≤ 10¹⁸.

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