Description

There is a pile of stones on the table. In each move, a player may take a prime number of stones. The player who cannot make a move loses. What is the minimum number of moves needed to win? (One move means one player's turn.) Assume both players play optimally: the player who can force a win will win as quickly as possible, and the losing player will delay as long as possible.

Input Format

The first line contains $N$, the number of test cases.

Each of the next $N$ lines contains the number of stones.

Output Format

For each test case, output one number. If the position is winning, output the minimum number of moves needed to win; otherwise, output $-1$.

3
8
9
16

1
-1
3

Hint

Constraints: the number of stones is $\leq 20000$, and $N \leq 10$.

Translated by ChatGPT 5