Remove Duplicates II Queries

You are given several queries. Each query contains a sorted array of integers. Your task is to remove duplicates from the array such that each element appears at most twice. The duplicate removal must be performed in-place, and you should return the new length of the modified array.

For a given query with an array nums, the algorithm can be described as follows:

For every element nums[i], if it is different from the element at position index - 2 (i.e. nums[index-2]), copy nums[i] to nums[index] and increment index. This ensures that each element appears at most twice.

Mathematically, we update as follows:

$$\text{{if }} nums[i] \neq nums[index-2] \text{{ then } } nums[index] = nums[i], \; index++ $$

You will be given Q queries. For each query, output the new length of the array after removing extra duplicates.

inputFormat

The input is read from stdin and has the following format:

Q
n1 a1 a2 ... an1
n2 b1 b2 ... bn2
...

Where:

• Q is the number of queries.
• Each query starts with an integer n representing the number of elements in the array, followed by n space-separated integers (sorted in non-decreasing order).

outputFormat

For each query, print a single integer on a new line which represents the new length of the array after removing extra duplicates. The results for all queries should be printed to stdout.

## sample

3
6 1 1 1 2 2 3
5 1 1 1 1 1
7 0 0 1 1 1 2 3

5
2
6

</p>