B. Circular Cone
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Zogbi is playing a video game, in which there is a circle divided into $$$n$$$ equal sectors, and initially each sector has a cone in it. She wins the game if she moves all the cones to any one specific sector in the minimum number of operations.

In one operation, she can select any two distinct cones and must move both of them independently to any one of their adjacent sectors from their current sector.

Note: two sectors are adjacent if they share a side in circular order.

For example, consider the case $$$n = 4$$$, as shown below. In each operation, she moves the two cones shown by red arrows to an adjacent sector. She makes exactly two operations to move all cones to one same sector. And it can be shown that one cannot do it in less than $$$2$$$ operations.

n = 4, operations are shown by red arrows.

Find the minimum number of operations. If it is impossible to move all cones to the same sector, output $$$-1$$$ instead.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1\le t \le 2\cdot10^5$$$). The description of the test cases follows.

The first line of each test case contains only one positive integer $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$), representing the number of sectors (so the cones).

Additionally, the sum of n over all the test cases doesn't exceed $$$2\cdot10^5$$$.

Output

For each test case, output a single line containing an integer  — the minimum number of operations to move all cones to one same sector. If it is impossible to move all cones to the same sector, then output $$$-1$$$ instead.

Example
Input
7
1
2
3
4
5
8
12
Output
0
-1
1
2
3
8
18
Note

The fourth test case is explained with a figure in the problem statement.