Problem M
Most Difficult

You are an expert on the most difficult field of math — primes! Indeed, you have actually proven the Riemann Hypothesis, but unfortunately, this margin is too narrow to contain the proof.

Being considered a prime expert, $q$ people have come to you for help. The $i$-th person has a favorite number $x_ i$, and they want to find the primmest prime number with respect to $x_ i$ — that is, the smallest prime number $p$ such that both $p$ and $x_ i + p$ are prime!

Unfortunately, there are too many people, and you don’t want to spend your time answering such trivial questions. Instead, you decide to write a program to answer all of their questions!

Input

The first line contains an integer $q$, denoting the number of people ($1 \leq q \leq 100$).

The next $q$ lines each contain an integer $x_ i$, denoting the favorite number of the $i$-th person ($1 \leq x_ i \leq 10^{18}$).

Output

Output $q$ lines, where the $i$-th line contains the primmest prime $p$ with respect to $x_ i$. If there is no such prime $p$ where both $p$ and $x_ i + p$ are primes, output $-1$ instead.

10
1
2
3
4
5
3233
4200
1000000000
969268337140823504
1000000000000000000

2
3
2
3
2
-1
11
7
2837
3