Halfway There
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.
Input data
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}).
Output data
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.
Examples
3 6 10 19
1 3 9