시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 512 MB | 48 | 35 | 29 | 70.732% |
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