Yes, Prime Minister

해커 씨가 이끄는 행정부(DAA)에는 무한히 많은 공무원이 있다. 모든 정수는 정확히 한 공무원의 ID(사번)로 쓰인다. 해커 씨는 공무원의 과잉 인력을 줄이려 하므로, ID가 $[l, r]$에 연속으로 들어오는 사람만 남기고 나머지는 모두 해고한다.

그런데 상임차관 험프리 경의 ID는 $x$이고, 그는 해고될 수 없으므로 $l \leq x \leq r$이어야 한다. 해커 씨는 총리가 되고 싶어 하므로, 남은 사람들의 ID 합 $\sum_{i = l}^{r} i$가 소수여야 한다고 요구한다.

당신 버나드는 두 상관의 요구를 모두 만족하는 감축 계획을 세워야 한다. 그렇지 않으면 해커 씨나 험프리 경이 당신을 해고할 것이다.

해커 씨는 가능한 한 적은 사람을 남기는 편을 좋아한다. 두 사람의 요구를 만족하면서 남길 수 있는 최소 인원을 계산하라.

소수 $p$는 $1$보다 큰 정수 가운데 $1$과 $p$ 외에 양의 약수를 갖지 않는 수이다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. ($1 \leq T \leq 10^6$)

이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄이자 유일한 줄에는 험프리 경의 ID $x_i$가 주어진다. ($-10^7 \leq x_i \leq 10^7$)

각 테스트 케이스마다 한 줄에 하나의 정수를 출력한다. 그러한 계획이 존재하면 남길 수 있는 최소 인원을, 존재하지 않으면 $-1$을 출력한다.