Ніколи тебе не покину#11534
По дорозі додому зі школи, Герман часто чув з вікон квартир популярну пісню «Ніколи тебе не покину» у виконанні Олександра Лосєва. Він настільки звик до неї, що може на слух визначити кількість вікон, з яких лунає ця пісня.
З вікна квартири Германа завжди грає пісня «Ніколи тебе не покину». Він запам'ятав, що його квартира є -ою за рахунком, з якої грає пісня, і що дріб \frac{k+1}{n+k} є скоротним для деякого цілого числа , причому це є мінімально можливим.
Вам потрібно визначити, якою за рахунком буде квартира Германа для заданого числа .
У першому рядку міститься ціле число q~(1 \leq q \leq 100) — кількість тестових прикладів.
Далі йде рядків, у кожному з яких міститься по одному цілому числу n~(3 \leq n \leq 10^{12}).
Вивід містить рядків. Кожен рядок містить єдине ціле число — відповідь на задачу.
Приклад 1