RoAlgo Educational Round #3 | Dailailailai💀💀💀💀

Lui Bahoi nu-i plac numerele impare. El are un vector cu $N$ elemente, și poate să facă următoarea operație de câte ori vrea:

• Alege un indice $i$, crește valorile vectorului de pe pozițiile $i, i + 1, \dots, n$ cu $1$.

Cerință

Care este numărul minim de operații ca la final să nu aibă numere impare în vector?

Date de intrare

Pe prima linie se află $t$, numărul de test cases. Pe prima linie a fiecărui test case se află un număr $N$, iar pe următoarea linie exact $N$ numere.

Date de ieșire

Se vor afișa $t$ linii, fiecare cu răspunsul test case-ului respectiv.

Restricții și precizări

• $1 \leq N,t \leq 2 \cdot 10^5$
• Elementele vectorului sunt naturale și nu depășesc $10^{18}$.
• Se garantează faptul că suma $N$-urilor pe toate testcase-urile este $\leq 2 \cdot 10^5$.

Exemplu

stdin

10
9
8 4 3 4 5 3 10 2 1
9
9 5 2 7 4 10 3 8 4
5
4 4 8 7 2
4
10 2 5 1
9
6 8 1 10 1 2 3 4 5
3
9 5 3
3
6 5 3
10
1 2 1 9 5 6 3 8 9 1
3
6 7 5
4
8 5 5 6

stdout

5
6
2
1
7
1
1
7
1
2