Dijkstra?

Cerință

Se dă un graf neorientat cu $n$ noduri, construit după următoarea regulă: există muchie de la $i$ la $j$ dacă și numai dacă $|i - j|$ este număr prim.

Să se afle lungimea celui mai scurt drum de la nodul $1$ la nodul $n$ sau să se afișeze $-1$ dacă acest lucru nu se poate realiza.

Date de intrare

Pe prima linie se va afla $t$, numărul de teste. Pe următoarele $t$ linii se vor afla valorile lui $n$, corespunzătoare fiecărui graf.

Date de ieșire

Pentru fiecare test, se va afișa răspunsul la întrebare sau $-1$, după caz.

Restricții și precizări

• $1 \leq t \leq 100$
• $1 \leq n \leq 10^9$

Exemplu

stdin

6
1
7
13
50
493
8

stdout

0
2
2
2
2
1