== include(page="template/taskheader" task_id="kdrum") ==

Laura este pasionata plimbarile prin parc. Fiind totusi o activitate lipsita de originalitate, ea si-a propus ca plimbarile ei sa urmeze un plan mai nastrusnic. Pentru a va ajuta, ea a reprezentat parcul sub forma unei matrici cu $N$ linii si $M$ coloane. Pentru fiecare zona din parc, ea i-a atribuit un numar natural dupa criterii numai de ea stiute. Zonele prin care nu poate trece le-a marcat cu $-1$. Acum ea se afla in pozitia $x1$ $y1$ si doreste sa ajunga la pozitia $x2$ $y2$ astfel incat produsul numerelor de pe drum sa fie divizibil cu un numar $K$. Pentru ca este frig afara, ea doreste sa stie care este lungimea minima a unui astfel de drum. Cum dorintele ei sunt porunci, voi trebuie sa o ajutati.

Laura este pasionata plimbarile prin parc. Fiind totusi o activitate lipsita de originalitate, ea si-a propus ca plimbarile ei sa urmeze un plan mai nastrusnic. Pentru a va ajuta, ea a reprezentat parcul sub forma unei matrici cu $N$ linii si $M$ coloane. Pentru fiecare zona din parc, ea i-a atribuit un numar natural pozitiv dupa criterii numai de ea stiute. Zonele prin care nu poate trece le-a marcat cu $0$. Acum ea se afla in pozitia $x1$ $y1$ si doreste sa ajunga la pozitia $x2$ $y2$ astfel incat produsul numerelor de pe drum sa fie divizibil cu un numar $K$. Pentru ca este frig afara, ea doreste sa stie care este lungimea minima a unui astfel de drum. Cum dorintele ei sunt porunci, voi trebuie sa o ajutati.

h2. Date de intrare

* $1 ≤ N ≤ 200$
* $1 ≤ M ≤ 200$
* $1 ≤ K ≤ 100 000 000$

* Elementele matricii sunt numere intregi cuprinse in intervalul $[0, 10 000]$.

* Pentru $40%$ din teste, $1 ≤ K ≤ 500$.
h2. Exemplu