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 2∣L∣-th element of L if ∣L∣ is even, and the 2∣L∣+1-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≤t≤103). Description of the test cases follows.
The only line of each test case contains a single integer n (2≤n≤1018).
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.