pdist

Cerință

În urma a $5$ minute de muncă continuă, celebrii frați matematicieni Srep și Pep au propus conceptul de distanță dintre două numere naturale cu același număr de cifre.

Această distanță este definită ca numărul de poziții unde cifrele corespunzătoare din cele două numere diferă. De exemplu, distanța dintre $10234$ și $20431$ este egală cu $3$, deoarece acestea diferă la cifra unităților, la cifra sutelor și la cifra zecilor de mii.

În urma succesului acestui concept, cei doi frați s-au gândit să studieze p-distanța a $t$ numere naturale. p-distanța unui număr natural $x$ este definită ca fiind distanța minimă dintre $x$ și oricare număr prim $p$ cu același număr de cifre ca $x$.

Din nefericire, p-distanța este greu de calculat pe hârtie. Din acest motiv, ai fost angajat în echipa lor de cercetare pentru a scrie un program care poate calcula p-distanța celor $t$ numere date.

Date de intrare

Pe prima linie a fișierului de intrare pdist.in se va afla un număr $t$ ($1 \le t \le 10$) — lungimea listei de numere studiate de frați.

Pe fiecare dintre următoarele $t$ linii se va afla câte un număr $n$ ($1 \le n < 1\,000\,000\,000$), pentru care va trebui să calculați p-distanța.

Date de ieșire

Fișierul de ieșire pdist.out va conține $t$ numere, \texttt{p-distanțele} celor $t$ numere din fișierul de intrare.

Restricții și precizări

Exemplul 1

pdist.in

5
1
200
89
95
8878

pdist.out

1
2
0
1
2

Explicație

• Distanța minimă dintre $1$ și un alt număr prim de o cifră, cum ar fi $2$, $3$, $5$ sau $7$, este egală cu $1$.
• Distanța minimă dintre $200$ și un alt număr prim de trei cifre este egală cu $2$. Exemple de numere prime de $3$ cifre aflate la distanța $2$ de $200$ sunt $107$, $211$ și $293$.
• $89$ este un număr prim, deci p-distanța acestuia este egală cu $0$.