== include(page="template/taskheader" task_id="4x4puzzle") ==

Poveste si cerinta...

Micutului Gigel ii plac puzzle-urile foarte mult. Acum cateva zile a descoperit traditionalul puzzle $4x4$. Acest puzzle consta din numerele de la $0$ la $15$, aranjate intr-un patrat cu $4$ linii si $4$ coloane. O mutare consta din interschimbarea a $2$ elemente adiacente pe orizontala sau verticala, cu conditia ca unul din elemente sa fie elementul $0$. Scopul puzzle-ului este de a ajunge in urmatoarea stare finala:
$
1  2  3  4
5  6  7  8
9 10 11 12
3 14 15  0
$
 
Fiind data starea initiala a puzzle-ului, determinati daca exista o secventa de mutari astfel incat puzzle-ul sa fie adusin starea finala.

h2. Date de intrare

...

Prima linie a fisierului de intrare $4x4puzzle.in$ contine numarul $P$ de puzzle-uri descrise in continuare. Fiecare puzzle consta din $4$ linii, pe care sunt afisate cate $4$ numere. Inaintea descrierii fiecarui puzzle exista o linie goala.

h2. Date de iesire

...

Pentru fiecare din cele $P$ puzzle-uri veti afisa in fisierul de iesire $4x4puzzle.out$ cate o linie continand sirul $"DA"$, daca puzzle-ul poate fi adus in starea finala, respectiv sirul $"NU"$ in caz contrar.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ P ≤ 100 000$

h2. Exemplu
table(example). |_. 4x4puzzle.in |_. 4x4puzzle.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

|2

h3. Explicatie
 
...

1 2 3 4
5 6 7 8
9 10 11 0
12 13 14 15
 
1 2 3 4
5 6 7 8
9 10 11 0
13 12 14 15
|NU
DA
|

== include(page="template/taskfooter" task_id="4x4puzzle") ==