I. If I Catch You
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
square loop for n = 6

Liola and Eastred are playing a chasing game on a square loop which consists of $$$4n-4$$$ grids, the size of the square is $$$n\times n$$$. Both Liola and Eastred can only move clockwise. In the beginning, Liola is at the upper right corner, and Eastred is at the bottom left corner.

The game is played in rounds, each round performs the following steps in order:

  1. Liola places a trap at his current position. Eastred can't move to the grids with traps, but Liola ignores these traps.
  2. Liola moves $$$2$$$ or $$$3$$$ grids.
  3. Eastred moves $$$1,2,3,$$$ or $$$4$$$ grids.

At any time (even if a round is not over), the game is over if it meets any one of the following conditions:

  • If all the $$$[1,4]$$$ grids that Eastred can move have traps, Eastred can't move, Liola wins.
  • If Liola and Eastred are at the same grid, Eastred catches Liola, Eastred wins.

Both Liola and Eastred will play optimally. Can Eastred wins? If he can, you should find the minimum number of rounds Eastred takes to win. In addition, If Liola can't win, he will try to make the number of rounds as large as possible.

Input

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ — the number of test cases.

Each test case is described by one integer $$$n$$$ $$$(1\leq n\leq 10^5)$$$ — the side length of the square loop.

Output

For each test case, output an integer in one line — If Eastred loses, output $$$-1$$$. Otherwise, output the minimum number of rounds Eastred takes to win.

Example
Input
2
1
2
Output
0
1
Note

In test case $$$1$$$, before the first round, Liola and Eastred are at the same grid. So Eastred catches Liola immediately, Eastred wins in $$$0$$$ round.

In test case $$$2$$$, the position of Liola and Eastred before the first round is as follows:

before start

In the first round, Liola has two choices, go to ③ or ④. If he goes to ③, he will be caught immediately. So Liola places a trap at ① and goes to ④. We use $$$X$$$ to represent the trap.

after Liola is walked

After Eastred moves $$$1$$$ grid clockwise, Liola and Eastred are at the same grid, Eastred catches Liola, Eastred wins in $$$1$$$ round.