H. На полпути
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано целое число $$$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$$$.

Пример
Входные данные
3
6
10
19
Выходные данные
1
3
9