410348: GYM104011 H Halfway There

Given an integer $$$n$$$, find the median of the list of all integers from $$$1$$$ to $$$n - 1$$$ that are coprime with $$$n$$$.

Recall that integers $$$a$$$ and $$$b$$$ are called coprime if their greatest common divisor is 1. The median of a list $$$L$$$ is defined to be the $$$\frac {|L|}{2}$$$-th element of $$$L$$$ if $$$|L|$$$ is even, and the $$$\frac {|L|+1}{2}$$$-th element of $$$L$$$ if $$$|L|$$$ is odd. Here $$$L$$$ is assumed to be sorted in ascending order, $$$|L|$$$ denotes the length of $$$L$$$, and indices are $$$1$$$-based.

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). Description of the test cases follows.

The only line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^{18}$$$).

For each test case, print a single integer — the median of the list of integers from $$$1$$$ to $$$n - 1$$$ that are coprime with $$$n$$$.

3
6
10
19

1
3
9