{"raw_statement":[{"iden":"problem statement","content":"An integer sequence that satisfies the following condition is called a **good sequence**.\n\n*   It is possible to perform the following **merge operation** zero or more times to make the sequence length $1$.\n    *   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.  \n        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)$.\n\nThere is a length-$N$ integer sequence $A = (A_1, A_2, \\dots, A_N)$.  \nYou can perform the following **insertion operation** zero or more times.\n\n*   Choose any integer $x$. Insert one $x$ at any position in $A$ (possibly the beginning or end).\n\nWhat 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.\nYou are given $T$ test cases; solve the problem for each of them."},{"iden":"constraints","content":"*   $1 \\leq T \\leq 2 \\times 10^5$\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq A_i \\leq 10^9$\n*   The sum of $N$ over all test cases is at most $2 \\times 10^5$.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format. Here, $\\mathrm{case}_i$ means the $i$\\-th test case.\n\n$T$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach test case is given in the following format:\n\n$N$\n$A_1$ $A_2$ $\\dots$ $A_N$"},{"iden":"sample input 1","content":"4\n3\n4 2 2\n1\n1\n5\n1 3 5 4 2\n10\n766294630 440423914 59187620 725560241 585990757 965580536 623321126 550925214 122410709 549392045"},{"iden":"sample output 1","content":"1\n0\n6\n1889132222\n\nFor the 1st test case, the sequence $(4, 2, 2, 3)$ obtained by inserting $3$ at the end of $A$ is a good sequence because it can be reduced to length $1$ by performing merge operations in the following steps.\n\n*   Remove the $2$s at the 2nd and 3rd positions and insert $2+1=3$. The sequence becomes $(4, 3, 3)$.\n*   Remove the $3$s at the 2nd and 3rd positions and insert $3+1=4$. The sequence becomes $(4, 4)$.\n*   Remove the $4$s at the 1st and 2nd positions and insert $4+1=5$. The sequence becomes $(5)$.\n\nIt is impossible to make $A$ a good sequence with fewer than one insertion operation, so the answer is $1$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}