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

Cunoasteti cu totii problema "clasica" a celor $N$ monede (numerotate de la $1$ la $N$), dintre care una este diferita (mai grea sau mai usoara). Pentru a identifica moneda diferita, aveti la dispozitie o balanta cu $2$ talere, cu care puteti efectua cantariri. O cantarire consta in amplasarea a aceluiasi numar de monede pe fiecare din cele $2$ talere (stang si drept). Rezultatul unei cantariri indica daca monedele (sau monezile) de pe cele $2$ talere au aceeasi greutate, daca cele de pe talerul stang sunt mai grele, sau daca cele de pe talerul drept sunt mai grele. Gigel a efectuat $M$ cantariri in vederea identificarii monezii diferite. Totusi, dupa ce a efectuat cele $M$ cantariri, el nu stie cum sa mai continue, astfel ca va cere ajutorul. Gigel ar vrea sa stie care este numarul minim suplimentar de cantariri ce mai trebuie efectuate pentru a identifica moneda diferita (cunoscand cantaririle efectuate in prealabil de Gigel, impreuna cu rezultatul acestora).

Cunoasteti cu totii problema "clasica" a celor $N$ monede (numerotate de la $1$ la $N$), dintre care una este diferita (mai grea sau mai usoara). Pentru a identifica moneda diferita (si a stii daca este mai grea sau mai usoara decat celelalte monezi), aveti la dispozitie o balanta cu $2$ talere, cu care puteti efectua cantariri. O cantarire consta in amplasarea a aceluiasi numar de monezi pe fiecare din cele $2$ talere (stang si drept). Rezultatul unei cantariri indica daca monezile de pe cele $2$ talere au aceeasi greutate, daca cele de pe talerul stang sunt mai grele, sau daca cele de pe talerul drept sunt mai grele. Gigel a efectuat $M$ cantariri in vederea identificarii monezii diferite. Totusi, dupa ce a efectuat cele $M$ cantariri, el nu stie cum sa mai continue, astfel ca va cere ajutorul. Gigel ar vrea sa stie care este numarul minim suplimentar de cantariri ce mai trebuie efectuate pentru a identifica moneda diferita, precum si de a sti daca este mai grea sau mai usoara decat celelalte monezi (cunoscand cantaririle efectuate in prealabil de Gigel, impreuna cu rezultatul acestora).

h2. Date de intrare

h2. Date de ieşire

În fişierul de ieşire $moneda.out$ veti afisa $T$ linii, cate una pentru fiecare test dat in fisierul de intrare (in ordinea in care sunt date testele). Pe linia corespunzatoare unui test veti afisa un singur numar, reprezentand numarul minim de cantariri suplimentare necesare pentru a identifica moneda diferita.

În fişierul de ieşire $moneda.out$ veti afisa $T$ linii, cate una pentru fiecare test dat in fisierul de intrare (in ordinea in care sunt date testele). Pe linia corespunzatoare unui test veti afisa un singur numar, reprezentand numarul minim de cantariri suplimentare necesare pentru a identifica moneda diferita (si a sti daca este mai grea sau mai usoara decat celelalte monezi).

h2. Restricţii