Crazy tea party

There are n participants seated around a table. In one minute, one neighboring pair can exchange places. Find the minimum number of minutes required to reverse the circular order, so every left neighbor becomes a right neighbor and vice versa.

Input

The first line contains the number of test cases. Each following line contains one integer n, where 1 \le n \le 32767.

Output

For each test case, print the minimum time in minutes.

Example

Input:

3
4
5
6

Output:

2
4
6