Halfway There

시간 제한2초메모리 제한512 MB

요약

n이 주어질 때마다 1부터 n-1까지 n과 서로소인 정수들의 중앙값을 구한다.

난이도: 보통10점 중 7점
유형: 정수론, 수학
정답자: 아직 제출이 없습니다

문제

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

예제1

예제 1
입력
```
3
6
10
19
```
예상 출력
```
1
3
9
```