P1857 Prime Stone Game

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.

The first line contains $N$, the number of test cases. Each of the next $N$ lines contains the number of stones.

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

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