Mad tea Party

N participants in the "mad tea party" sit around the table. Every minute, one pair of neighbors in the table can be swapped. Find the minimum time (in minutes) necessary to ensure that all participants in tea parties were transferred in the reverse order (ie, the left neighbor should be a right, and right - left).

Input

The input file in the first line contains the number of tests. Each subsequent line contains one integer N (1 ≤ N ≤ 32767) - the number of participants in a mad tea party.

Output

In the output file display on a separate line for each number N of the minimum time required for the transplantation of all N participants.

Examples