Halfway There#11139
Given an integer , find the median of the list of all integers from to n - 1 that are coprime with .
Recall that integers and are called coprime if their greatest common divisor is 1. The median of a list is defined to be the \frac {|L|}{2}-th element of if is even, and the \frac {|L|+1}{2}-th element of if is odd. Here is assumed to be sorted in ascending order, denotes the length of , and indices are -based.
Each test contains multiple test cases. The first line contains the number of test cases (1 \le t \le 10^3). Description of the test cases follows.
The only line of each test case contains a single integer (2 \le n \le 10^{18}).
For each test case, print a single integer — the median of the list of integers from to n - 1 that are coprime with .
Example 1