Hacker 先生的行政事务部（DAA）拥有无限多的公务员。每一个整数都被用作一名公务员的 ID（身份编号）。Hacker 先生热衷于精简公务员队伍，因此他只会保留 ID 在 $[l, r]$ 范围内的连续人员，并解雇其他人。

然而，常务秘书 Sir Humphrey 的 ID 是 $x$，他不能被解雇，因此必须满足 $l \le x \le r$。Hacker 先生想要成为首相，所以他要求保留人员的 ID 之和 $\sum_{i=l}^{r} i$ 必须是一个质数。

你，Bernard，需要制定一个满足两位老板要求的裁员计划。否则，Hacker 先生或 Sir Humphrey 就会解雇你。

Hacker 先生希望保留尽可能少的人。请计算满足他们要求时，最少需要保留的人数。

质数 $p$ 是指一个大于 1 的整数，除了 1 和 $p$ 以外没有其他正整数因子。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^6$)，表示测试用例的数量。接下来是 $T$ 个测试用例。 每个测试用例的第一行包含一个整数 $x_i$ ($-10^7 \le x_i \le 10^7$)，即 Sir Humphrey 的 ID。

输出格式

对于每个测试用例，输出一行一个整数：如果存在这样的计划，输出最少保留的人数；否则输出 $-1$。

样例

输入 1

10
-2
-1
0
1
2
3
4
5
6
7

输出 1

6
4
3
2
1
1
2
1
2
1