Description

桌上有若干个石子，每次可以取质数个。谁先取不了，谁就输。问最少几步能赢？（一个人取一次算一步）假设双方都使用最优策略，且必胜方会尽量快地取胜，必败方会尽可能拖延步数。

Input Format

第一行 $N$，表示有 $N$ 组数据

接下来 $N$ 行为石子数

Output Format

每组数据一个数，若必胜，则输出最少步数，否则输出 $-1$。

3
8
9
16

1
-1
3

Hint

石子数 $\leq 20000$，$N\leq 10$