D. Pizzas
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have a perfectly circular pizza. You will make straight cuts: each cut is an infinite straight line (like the complete path of a knife) that goes through the pizza.

Given a natural number $$$N$$$, your goal is to determine the minimum number of straight cuts needed to obtain exactly $$$N$$$ pieces of pizza, or print $$$-1$$$ if it is impossible. The pieces do not need to have the same size or the same shape.

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 10^5$$$), the number of test cases.

Each of the next $$$T$$$ lines contains an integer $$$N$$$ ($$$1 \le N \le 10^5$$$).

Output

For each test case, print an integer: the minimum number of straight cuts needed to obtain exactly $$$N$$$ pieces, or $$$-1$$$ if it is not possible.

Example
Input
3
3
10
1
Output
2
4
0