На півдорозі

Дано ціле число $n$. Потрібно знайти медіану списку всіх цілих чисел від $1$ до $n-1$, які є взаємно простими з $n$.

Нагадаємо, що два цілі числа $a$ і $b$ є взаємно простими, якщо їхній найбільший спільний дільник дорівнює 1. Медіаною списку $L$ називається $\frac{|L|}{2}$-й елемент списку $L$, якщо $|L|$ парне, і $\frac{|L|+1}{2}$-й елемент списку $L$, якщо $|L|$ непарне. Тут вважається, що $L$ відсортований у порядку зростання, $|L|$ позначає довжину $L$, а індекси починаються з $1$.

Вхідні дані

Кожен тест містить кілька тестових випадків. У першому рядку вказано кількість тестових випадків $t$ ($1\le t\le 10^3$). Далі йде опис кожного тестового випадку.

Єдиний рядок кожного тестового випадку містить одне ціле число $n$ ($2\le n\le 10^{18}$).

Вихідні дані

Для кожного тестового випадку виведіть одне ціле число — медіану списку цілих чисел від $1$ до $n-1$, які є взаємно простими з $n$.

Приклади