pdist

Time limit: 0.1s Memory limit: 64MB Input: pdist.in Output: pdist.out

Cerință

În urma a 55 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 1023410234 și 2043120431 este egală cu 33, 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 tt numere naturale. p-distanța unui număr natural xx este definită ca fiind distanța minimă dintre xx și oricare număr prim pp cu același număr de cifre ca xx.

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 tt numere date.

Date de intrare

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

Pe fiecare dintre următoarele tt linii se va afla câte un număr nn (1n<10000000001 \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 tt numere, \texttt{p-distanțele} celor tt numere din fișierul de intrare.

Restricții și precizări

# Punctaj Restricții
1 10 n<10n < 10
2 30 n<1000n < 1\,000
3 25 n<100000n < 100\,000
4 20 n<1000000n < 1\,000\,000
5 15 Fără restricții suplimentare

Exemplul 1

pdist.in

5
1
200
89
95
8878

pdist.out

1
2
0
1
2

Explicație

  • Distanța minimă dintre 11 și un alt număr prim de o cifră, cum ar fi 22, 33, 55 sau 77, este egală cu 11.
  • Distanța minimă dintre 200200 și un alt număr prim de trei cifre este egală cu 22. Exemple de numere prime de 33 cifre aflate la distanța 22 de 200200 sunt 107107, 211211 și 293293.
  • 8989 este un număr prim, deci p-distanța acestuia este egală cu 00.

Log in or sign up to be able to send submissions!