Ținut

Într-o lume îndepărtată la marginea unei păduri întunecate se afla un ținut mistic cunoscut sub numele de "Țara Vrăjitorilor". Acolo, printre copaci uriași și pietre ancestrale, trăiau ființe magice și misterioase despre care se spune că au puteri nebănuite.

Acest ținut, renumit pentru magia lui, poate fi traversat după niște reguli stricte. Ținutul este împărțit în comitate, fiecare comitat este condus de o ființă magică. Fiecare ființă magică are o putere înnăscută pe care o vom numi în continuare factorul $X$. O ființă poate trece printr-un comitat doar dacă îndeplinește niște reguli stricte legate de factorul său $X$, dar și de factorul $X$ al conducătorului ținutului respectiv.

Harta unui astfel de ținut este reprezentată sub forma unei matrice cu $N$ linii și $N$ coloane în care fiecare celulă reprezintă un comitat, iar $a_{i,j}$ reprezintă valoarea factorului $X$ pentru ființa magică ce conduce comitatul de coordonate $(i, j)$. Deplasarea pe hartă se face în direcțiile date de cele 4 puncte cardinale (N, E, S, V).

Un tânăr voinic vrea să traverseze ținutul pornind din celula $(1, 1)$ și ajungând în celula $(N, N)$, însă nu știe dacă poate să facă acest lucru și are nevoie de ajutorul vostru.

Cerință

Știind factorul $X$ al tânărului și faptul că pentru a putea trece printr-un comitat factorul său $X$ trebuie să aibă cel puțin atâția divizori câți are factorul $X$ al conducătorului:

1. Determinați lungimea unui drum prin care acesta poate să parcurgă ținutul după regulile menționate astfel încât această lungime să fie minimă;
2. Determinați costul minim de parcurgere al ținutului, având în vedere că tânărul trebuie să plătească o sumă de bani egală cu diferența dintre numărul de divizori al factorului său $X$ și numărul de divizori al factorului $X$ al ființei conducătoare.

Știind că pentru a traversa un comitat factorul $X$ al tânărului trebuie să fie strict mai mare decât al conducătorului:

3. Aflați factorul $X$ minim pe care îl poate avea tânărul astfel încât să poată traversa ținutul în siguranță.

Date de intrare

Pe prima linie un număr $C$ reprezentând cerința care trebuie rezolvată.

Pe a doua linie un număr $T$ reprezentând numărul de cazuri distincte ce trebuie rezolvate.

Apoi se vor citi $T$ grupuri de forma:

• Pentru cerințele 1 și 2, prima linie va conține un număr reprezentând factorul $X$ al tânărului.
• Pe următoarea linie un număr $N$ cu semnificația de mai sus.
• Pe următoarele $N$ linii se vor afla elementele matricei.

Date de ieșire

Fișierul de ieșire va conține $T$ linii. Fiecare linie conține răspunsul pentru cazul de testare corespunzător.

Restricții și precizări

• Dacă nu există niciun drum care să respecte regulile date, se va afișa $-1$.
• Se garantează că tânărul va putea intra tot timpul în celula $(1, 1)$.
• $C \in \{1, 2, 3\}$
• Pentru $C = 1$ și $C = 2$, $a_{i,j} \geq 1$.
• $1 \leq T \leq 10$
• $1 \leq X \leq 10^{12}$
• $1 \leq N \leq 500$
• $0 \leq a_{i,j} \leq 10^{12}$
• Pentru teste în valoare de $10$ puncte, $C = 1$ și $1 \leq a_{i,j}, X \leq 10^{6}$.
• Pentru alte teste în valoare de $23$ de puncte, $C = 1$.
• Pentru alte teste în valoare de $10$ puncte, $C = 2$ și $1 \leq a_{i,j}, X \leq 10^{6}$.
• Pentru alte teste în valoare de $24$ de puncte, $C = 2$.
• Pentru alte teste în valoare de $10$ puncte, $C = 3$ și $1 \leq N \leq 300$, $0 \leq a_{i,j} \leq 10^{4}$.
• Pentru alte teste în valoare de $23$ de puncte, $C = 3$.

Exemplul 1

tinut.in

1
2
16
6
1 36 79 85 87 82
26 46 55 39 74 19
89 73 65 31 36 18
99 39 8 17 47 58
6 44 80 29 73 90
54 40 79 57 19 11
16
6
1 36 79 85 87 82
26 46 55 39 74 19
89 73 65 31 36 18
99 39 8 12 47 58
6 44 80 29 73 90
54 40 79 57 19 11

tinut.out

11
-1

Explicație

Pentru primul exemplu, la primul caz, vom considera o matrice în care notăm cu $0$ locurile pe unde se poate trece și cu $\textcolor{blue}{1}$ locurile pe unde nu se poate trece, numărul de divizori al factorului $X$ al tânărului fiind $5$.

Iar în al doilea caz, se poate observa că nu există drum de la $(1, 1)$ la $(N, N)$ care să satisfacă condițiile.

Exemplul 2

tinut.in

2
1
16
6
3 36 79 85 87 82
26 46 55 39 74 19
89 73 65 31 36 18
99 39 8 17 47 58
6 44 80 29 73 90
54 40 79 57 19 11

tinut.out

21

Explicație

Pentru al doilea exemplu, așa arată harta, în care valoarea din fiecare celulă reprezintă fie faptul că nu se poate trece prin comitat ($\textcolor{blue}{\text{x}}$), fie costul trecerii prin acel comitat. Se poate observa drumul urmat pentru a obține costul minim.

Exemplul 3

tinut.in

3
1
6
0 36 79 85 87 82
26 46 55 39 74 19
89 73 65 31 36 18
99 39 8 17 47 58
6 44 80 29 73 90
54 40 79 57 19 11

tinut.out

58

Explicație

Pentru al treilea exemplu, există mai multe variante prin care se poate parcurge ținutul de către un tânăr cu factorul $X = 58$, dar nu există niciuna în care să putem parcurge ținutul cu un factor mai mic. Un astfel de drum este: