Sport

Dupa eşecul de la olimpiadă, Chuck Nirros şi-a găsit alinarea în minunatele sendvişuri de la OverWay. Conştient că se îngraşă, s-a decis să se înscrie la ore de sport cu un antrenor calificat. Antrenamentul se desfăşoară pe parcursul a $T$ zile, în fiecare zi fiind prezenţi un număr diferit de elevi $N_i$. Antrenorul are un mod unic de a alege ordinea în care elevii vor folosi aparatele: la începutul fiecărei zile îşi va alege un număr natural nenul secret $K_i$, apoi elevii se aliniază într-un şir şi sunt numerotaţi de la stânga la dreapta începând cu $1$, reprezentând cel mai din stânga elev, şi terminând cu $N_i$, reprezentând cel mai din dreapta elev. El începe ulterior să îi numere de la stânga la dreapta, iar când ajunge la unul dintre capete îşi continuă numărătoarea pornind din acel capăt şi continuând către capătul opus.
Spre exemplu, pentru $N_i=3$, el va număra în felul următor: $1 \ 2 \ 3 \ 3 \ 2 \ 1 \ 1 \ 2 \ 3 \ 3 \ 2 \ 1 \dots$ . La fiecare $K_i$, elevul pe care se opreşte este eliminat complet din şir şi i se permite folosirea aparatelor de antrenament. Din păcate, Chuck Nirros nu cunoaşte numerele secrete, dar cunoaşte ordinea în care elevii au fost eliminaţi din şir.

Cerință

Dându-se ordinea elevilor eliminaţi în fiecare din cele $T$ zile, aflaţi cea mai mică valoare pe care o poate lua fiecare dintre numerele secrete $K_i$.

Date de intrare

Fişierul sport.in conţine pe prima linie numărul de zile $T$. Următoarele $2 \cdot T$ linii conţin ordinea în care elevii au fost eliminaţi în fiecare dintre cele $T$ zile şi vor avea următoarea configuraţie:

• linia $2 \cdot i$ conţine numărul de elevi prezenţi la antrenament în ziua $i$, notat cu $N_i$.
• linia $2 \cdot i+1$ conţine $N_i$ numere naturale separate prin câte un spaţiu, reprezentând ordinea în care elevii au fost eliminaţi în ziua $i$. Evident, numerele de pe această linie sunt diferite două câte două.

Date de ieșire

Fişierul sport.out conţine $T$ numere natural nenule reprezentând valorile minime pe care le pot lua fiecare dintre numerele secrete $K_i$, câte una pe linie.

Restricții și precizări

• $1 \leq T \leq 1 \ 002$
• $1 \leq N_i \leq 42$
• Atenţie! Numerele secrete sunt numere naturale nenule.

Exemplu

sport.in

2
2
2 1
6
2 4 6 3 1 5

sport.out

2
2

Explicație

Pentru prima zi un alt raspuns posibil este $3$, dar nu este minimal.

Pentru a doua zi, şirul elevilor va arăta în modul următor:

• $1 \ 2 \ 3 \ 4 \ 5 \ 6$ – la început
• $1 \ 3 \ 4 \ 5 \ 6$ – dupa ce sunt număraţi $1 \ 2$
• $1 \ 3 \ 5 \ 6$ – dupa ce sunt număraţi $3 \ 4$
• $1 \ 3 \ 5$ – dupa ce sunt număraţi $5 \ 6$
• $1 \ 5$ – dupa ce sunt număraţi $5 \ 3$
• $5$ – dupa ce sunt număraţi $1 \ 1$