D. Path Split
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a sequence of $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$.

You would like to partition $$$a$$$ into several subsequences$$$^{\text{∗}}$$$ $$$b_1,b_2,\ldots,b_k$$$, satisfying the following conditions:

  • Each element in $$$a$$$ belongs to exactly one of $$$b_i$$$.
  • For each sequence $$$b_i$$$, let its elements be $$$b_{i,1},b_{i,2},\ldots,b_{i,p_i}$$$. For every $$$1\le j \lt p_i$$$, $$$|b_{i,j}-b_{i,j+1}|=1$$$ should hold.

Please calculate the minimum number of subsequences you can partition $$$a$$$ into.

$$$^{\text{∗}}$$$A sequence $$$b_i$$$ is a subsequence of a sequence $$$a$$$ if $$$b_i$$$ can be obtained from $$$a$$$ by the deletion of several (possibly, zero or all) element from arbitrary positions.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le10^6$$$) — the length of the sequence $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le2n$$$) — the sequence $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print a single integer on one line — the minimum number of subsequences $$$a$$$ can be partitioned into.

Example
Input
7
1
1
1
2
8
11 13 10 11 11 11 13 10
6
8 8 6 7 7 7
3
5 1 3
10
11 14 14 13 12 14 12 10 14 12
1
2
Output
1
1
5
3
3
7
1
Note

In the first test case, we can partition $$$a$$$ into subsequences $$$[1]$$$. It is obvious that we cannot partition $$$a$$$ into fewer subsequences; thus, $$$1$$$ is the answer.

In the third test case, we can partition $$$a$$$ into subsequences $$$[11,10,11,10],[13],[11],[11],[13]$$$. Please note that $$$[11,10,11,11,11,10]$$$ is not a valid sequence, since $$$|11-11|=0\neq1$$$.