Ніколи тебе не покину

По дорозі додому зі школи, Герман часто чув з вікон квартир популярну пісню «Ніколи тебе не покину» у виконанні Олександра Лосєва. Він настільки звик до неї, що може на слух визначити кількість вікон, з яких лунає ця пісня.

З вікна квартири Германа завжди грає пісня «Ніколи тебе не покину». Він запам'ятав, що його квартира є $k$-ою за рахунком, з якої грає пісня, і що дріб $\frac{k+1}{n+k}$ є нескоротним для деякого цілого числа $n$, причому це $k$ є мінімально можливим.

Вам потрібно визначити, якою за рахунком буде квартира Германа для заданого числа $n$.

Вхідні дані

У першому рядку міститься ціле число $q(1\le q\le 100)$ — кількість тестових прикладів.

Далі йде $q$ рядків, у кожному з яких міститься по одному цілому числу $n(3\le n\le 10^{12})$.

Вихідні дані

Вивід містить $q$ рядків. Кожен рядок містить єдине ціле число $k$ — відповідь на задачу.

Приклади