== 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ă, 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 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ă, ş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).
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.in$ 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

h2. Exemplu

table(example). |_. cclj.in |_. cclj.out |

table(example). |_. cclj.în |_. cclj.out |

| 2
10 10
8 9