Problem Statement

An integer sequence that satisfies the following condition is called a good sequence.

• It is possible to perform the following merge operation zero or more times to make the sequence length $1$.
• Choose a location where two consecutive elements have equal values. Let $x$ be the value of those elements. Remove both elements and insert $x+1$ at the location where the elements were. For example, if we perform a merge operation on the 2nd and 3rd elements of the sequence $(1, 3, 3, 5)$, the sequence after the operation will be $(1, 4, 5)$.

There is a length-$N$ integer sequence $A = (A_1, A_2, \dots, A_N)$. You can perform the following insertion operation zero or more times.

• Choose any integer $x$. Insert one $x$ at any position in $A$ (possibly the beginning or end).

What is the minimum number of insertion operations needed to make $A$ a good sequence? For any $N$ and $A$ satisfying the constraints, it is possible to make $A$ a good sequence with a finite number of insertion operations.

You are given $T$ test cases; solve the problem for each of them.

Constraints

• $1 \leq T \leq 2 \times 10^5$
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• The sum of $N$ over all test cases is at most $2 \times 10^5$.
• All input values are integers.

Input

The input is given from Standard Input in the following format. Here, $\mathrm{case}_i$ means the $i$-th test case.

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N
A_1 A_2 \dots A_N

Output

Output $T$ lines. The $i$-th line should contain the answer for the $i$-th test case. For each test case, output the minimum number of insertion operations needed to make $A$ a good sequence.