Heist

Ștefan și Tudor nu erau hoți obișnuiți. Ei erau genii în informatică și matematică, pasionați de provocări logice și labirinturi criptate. Într-o seară misterioasă, au primit un mesaj anonim:

Banca Centrală din Matrizopolis păstrează în seiful său cel mai valoros artefact digital: Cheia Primă, o secvență binară ce poate decripta orice algoritm. Seiful este protejat de un sistem de securitate sub formă de... matrice.

Matricea avea dimensiunea $N\times N$, iar fiecare celulă reprezenta un pas posibil prin bancă. Sistemul avea o particularitate:

• Dacă valoarea unei celule era un număr prim, însemna că zona respectivă era plină de lasere invizibile – deci necesita efort și timp (cost 1).
• Dacă nu era prim, zona era sigură – fără riscuri (cost 0).

Pentru a ajunge la artefact, cei doi trebuiau să răspundă mai multor interogări transmise de sistemul bancar:

Care este drumul de efort minim de la celula $(i,j)$ la celula $(k,l)$?

Orice pas într-o celulă primă le consuma timp prețios, deci trebuiau să evite cât mai multe astfel de celule. Mișcările erau permise în cele 4 direcții: sus, jos, stânga și dreapta.

Pe măsură ce răspundeau la fiecare întrebare, ușile băncii se deschideau una câte una. Dar sistemul nu ierta greșeli: o alegere neinspirată într-o celulă primă le putea declanșa alarma.

Sarcina ta este să fii creierul din spatele operațiunii și să-i ajuți pe Ștefan și Tudor să:

• Calculeze drumul optim dintre două puncte din matrice, evitând cât mai multe numere prime.
• Răspundă la toate interogările sistemului pentru a ajunge la Cheia Primă fără a fi prinși.

Cerință

Dându-se o matrice $A$ cu $N$ linii și $N$ coloane, determinați pentru fiecare interogare drumul de cost minim din celula $A_{i, j}$ la celula $A_{k, l}$. Costul unei celule e:

• $1$, dacă valorea celulei e număr prim;
• $0$, altfel.

Date de intrare

Fișierul de intrare heist.in conține:

• pe prima linie un singur număr natural, $N$, cu semnificația din enunț;
• pe următoarele $N$ linii câte $N$ numere naturale, reprezentând numerele asociate zonelor în ordinea corespunzătoare elementelor din matrice, linie cu linie, de sus în jos, și de la stânga la dreapta pe fiecare linie;
• pe următoarea linie numărul $Q$, cu semnificația din enunț;
• pe următoarele $Q$ linii câte patru numere naturale, $i, j, k, l$, cu semnificația din enunț;
  Numerele aflate pe aceeași linie a fişierului sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire heist.out conține pe $Q$ linii costul drumului de cost minim între celulele date, câte un singur număr pe linie, în ordinea citirii.

Restricții și precizări

• $1 \leq N \leq 90$;
• $1 \leq Q \leq 10^{6}$;
• $0 \leq A_{i, j} \leq 2 \cdot 10^{9}, 1\leq i, j \leq N$.

Exemplu

heist.in

3
4 3 6
1 2 7
4 3 9
1
1 1 3 3

heist.out

1

Explicație

Vom merge jos, jos, dreapta, dreapta.