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

Neînfricatul $K0Kalaru 47$ a dat din nou lovitura. 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 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).

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

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

* **Full Feedback!**

* **Subtask 1 (20 puncte):** $N, M ≤ 20$
* **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$

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") ==