Given an integer , find the median of the list of all integers from to 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 -th element of if is even, and the -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 (). Description of the test cases follows.
The only line of each test case contains a single integer ().
For each test case, print a single integer — the median of the list of integers from to that are coprime with .