Info Winter Speed Code 2023 - Clasele XI-XII | Dijkstra?

This was the problem page during the contest. Access the current page here.
Time limit: 1s Memory limit: 16MB Input: Output:

Cerință

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

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

Date de intrare

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

Date de ieșire

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

Restricții și precizări

  • 1t1001 \leq t \leq 100
  • 1n1091 \leq n \leq 10^9

Exemplu

stdin

6
1
7
13
50
493
8

stdout

0
2
2
2
2
1

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