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

Neînfricatul $K0Kalaru 47$ a dat din nou lovitură. Acesta s-a calificat la renumita competiţie internaţională, şi anume la $JBOI$. Întrucât $K0Kalaru 47$ a investit foarte mult în pregătirea să de adevărat olimpic, acesta nu mai are cu ce să vină la competiţie, prin urmare a împrumutat un cal de la vecinul sau, Sorinel. $K0Kalaru 47$ nu este bun la geografie, aşa că este de datoria voastră să-l ajutaţi să ajungă. Dar, ghiciţi ce! el a devenit atât de bun în ultimul an încât dacă acesta ajunge la competiţie o să ia $MAXIM$ (şi evident primul loc). Acest lucru nu trebuie lăsat să se întâmple (doar echipa României are voie să ia $MAXIM$), aşa că voi trebuie să-i daţi $K0Kalarului 47$ un traseu cât mai lung că să nu reuşească să ajungă la timp la $JBOI$. Din nefericire, pe cât de praf este el la geografie, pe atât de bună memorie are. Aşa că voi trebuie să-i daţi un traseu cât mai lung şi care nu trece printr-un loc de mai multe ori (altfel acesta o să se prindă că l-aţi măsluit).
Suprafaţă pe care poate călători $K0Kalaru 47$ (acesta stă cam prost cu actele de identitate şi nu are voie să părăsească regiunea est-europeană) are formă unei table $NxM$. Calul $K0Kalarului 47$ poate să se deplaseze doar în formă de $L$ (exact cum o fac toţi caii de pe lumea asta). Scopul vostru este să generaţi o serie de mutări de cal cu cardinal maxim. Puteţi începe şi termină oriunde, dar la punctare se va ţine cont dacă s-a început şi/sau terminat în colţuri.

Neînfricatul $K0Kalaru 47$ a dat din nou lovitura. Acesta s-a calificat la renumita competiţie internaţională $JBOI$. Întrucât $K0Kalaru 47$ a investit foarte mult în pregătirea sa de adevărat olimpic, acesta nu mai are cu ce să vină la competiţie, prin urmare a împrumutat un cal de la vecinul său, Sorinel. $K0Kalaru 47$ nu este bun la geografie, aşa că este de datoria voastră să-l ajutaţi să ajungă. Dar, ghiciţi ce! el a devenit atât de bun în ultimul an încât dacă acesta ajunge la competiţie o să ia $MAXIM$ (şi evident primul loc). Acest lucru nu trebuie lăsat să se întâmple (doar echipa României are voie să ia $MAXIM$), aşa că voi trebuie să-i daţi $K0Kalarului 47$ un traseu cât mai lung ca să nu reuşească să ajungă la timp la $JBOI$. Din nefericire, pe cât de praf este el la geografie, pe atât de bună memorie are. Aşa că voi trebuie să-i daţi un traseu cât mai lung şi care nu trece printr-un loc de mai multe ori (altfel acesta o să se prindă că l-aţi măsluit).
Suprafaţa pe care poate călători $K0Kalaru 47$ (acesta stă cam prost cu actele de identitate şi nu are voie să părăsească regiunea est-europeană) are formă unei table $NxM$. Calul $K0Kalarului 47$ poate să se deplaseze doar în formă de $L$ (exact cum o fac toţi caii de pe lumea asta). Scopul vostru este să generaţi o serie de mutări de cal cu cardinal maxim. Puteţi începe şi termina oriunde, dar la punctare se va ţine cont dacă s-a început şi/sau terminat în colţuri.

h2. Date de intrare

Fişierul de intrare $cclj.în$ conţine un număr $t$ care semnfica numărul de teste. Pe următoarele $t$ linii se află câte două numere $N$ şi $M$ despărţite printr-un spaţiu, reprezentând dimensiunea tablei.

Fişierul de intrare $cclj.în$ conţine un număr $t$ care semnfică numărul de teste. Pe următoarele $t$ linii se află câte două numere $N$ şi $M$ despărţite printr-un spaţiu, reprezentând dimensiunea tablei.

h2. Date de ieşire

* $1 ≤ t ≤ 10$
* $8 ≤ N, M ≤ 500$

* **Full Feedback!**

* **Subtask 1 (20 puncte):** $N, M ≤ 20$

* **Subtask 2 (20 puncte):** $N = M, N$ da restul $1$ la împărţirea cu $4$

* **Subtask 2 (20 puncte):** $N = M, N$ dă restul $1$ la împărţirea cu $4$

* **Subtask 3 (20 puncte):** $N = M, N$ este o putere de $2$
* **Subtask 4 (40 puncte):** Restricţii iniţiale
h2. Punctaj

Punctajul obţinut pe un test este: <tex> punctaj = (\frac{K}{NrMax})^{2}*Pointspertest </tex>, unde $K$ este cel de mai sus, $NrMax$ este numărul maxim de căsuţe prin care se poate trece în condiţiile de mai sus, iar $Pointspertest$ rerezinta câte puncte valorează testul ( $70%$ din punctajul maxim acordat testului dacă niciunul dintre capete nu este într-un colţ, $85%$ pentru un capăt şi $100%$ pentru ambele) .

Punctajul obţinut pe un test este: <tex> punctaj = (\frac{K}{NrMax})^{2}*Pointspertest </tex>, unde $K$ este cel de mai sus, $NrMax$ este numărul maxim de căsuţe prin care se poate trece în condiţiile de mai sus, iar $Pointspertest$ reprezintă câte puncte valorează testul ( $70%$ din punctajul maxim acordat testului dacă niciunul dintre capete nu este într-un colţ, $85%$ pentru un capăt şi $100%$ pentru ambele) .

Punctajul final este suma punctajelor obţinute la fiecare test.
h2. Exemplu

| 2
10 10
8 9

|6
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 2 0 0 0 0 0
0 0 0 0 0 0 3 0 0 0
0 0 0 0 0 0 0 0 4 0
0 0 0 0 0 0 5 0 0 0
0 0 0 0 0 0 0 0 6 0

|7
1 0 0 0 0 0 0 0 0 0
0 0 2 0 0 0 0 0 0 0
0 0 0 0 3 0 0 0 0 0
0 0 0 0 0 0 4 0 0 0
0 0 0 0 0 0 0 0 5 0
0 0 0 0 0 0 6 0 0 0
0 0 0 0 0 0 0 0 7 0

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

h3. Explicaţie

**Atentie!**: Exemplul nu obtine 10 puncte si nici drumurile nu au lungime optima.
 

În exemplu, presupunând că ar valora 10 puncte, fiecăruia din teste îi vor fi atrbuite câte 5 puncte. În acest caz la primul test se va pleca din punctajul de 0.85 * 5 = 4.25 puncte, în timp ce la al doilea test se va pleca din punctajul de 1.0 * 5 = 5 puncte.
== include(page="template/taskfooter" task_id="cclj") ==