A. Delete the Array
time limit per test
2 s
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an integer array of $$$n$$$ elements $$$a_1, a_2, \dots, a_n$$$. You can perform two types of operations on it:

  1. Delete the minimum element of the array; if there are several minimums, you can choose which one to delete.
  2. Delete the first two elements of the array if they are equal. This operation can be performed only if the array contains at least two elements.
The array shrinks after deletions. For example, if the array is $$$[5, 2, 5, 2, 2, 4]$$$ and you perform the first operation on the second element, it becomes $$$[5, 5, 2, 2, 4]$$$.

You can perform any operations any number of times and in any order. What is the minimum number of operations you need to make the array empty?

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the size of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the array itself.

Additional constraint on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print one integer — the minimum number of operations to make the array $$$a$$$ empty using the operations above.

Example
Input
5
1
1
2
2 2
6
5 2 5 2 2 4
6
5 5 5 5 1 1
5
4 1 1 1 4
Output
1
1
4
3
4
Note

In the first test case, you can perform only the first operation once.

In the second test case, since the first two elements are equal, you can perform the second operation once and delete both elements.

In the third test case, it's optimal to perform the first operation and delete $$$a_2 = 2$$$. After that, you'll get the array $$$[5, 5, 2, 2, 4]$$$, and you can perform the second operation two times. In the result, you'll get the array $$$[4]$$$, so you need one more operation of the first type.