24645번 - 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$.

제한

힌트