eolymp
bolt
Try our new interface for solving problems
Problems

Halfway There

Halfway There

Time limit 2 seconds
Memory limit 512 MiB

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

Input example #1
3
6
10
19
Output example #1
1
3
9
Author Artem Vasilyev