Maximizing Task Assignments with Peer Review

You are organizing a contest where each task must be completed and then reviewed by another participant. In each test case, you are given n participants. Each participant is classified as either an individual competitor (denoted with 1) or a team competitor (denoted with 2). To ensure high quality, tasks are formed by pairing participants so that one reviews the work of the other. However, because no one can review their own work, tasks can only be formed in pairs.

Your goal is to determine the maximum number of tasks that can be assigned. Note that if n is odd, one participant will be left unpaired. In other words, the maximum number of tasks is given by the formula:

$$\text{MaxTasks} = 2\left\lfloor \frac{n}{2} \right\rfloor $$

However, there is a nuance based on the type of participant. When the number of individual competitors (denoted by 1) exceeds the number of team competitors (denoted by 2), pairing is straightforward because of their review constraints. Otherwise, if team competitors are more or equal in number, one might need to leave one out if the imbalance would cause an extra unpaired participant. Your task is to compute the maximum number of tasks that can be assigned given these rules.

inputFormat

The first line of input contains a single integer t (t ≥ 1), the number of test cases. For each test case:

• The first line contains an integer n (n ≥ 1), the number of participants.
• The second line contains n space-separated integers (each either 1 or 2) representing the type of each participant.

All input is read from standard input (stdin).

outputFormat

For each test case, output a single line containing the maximum number of tasks that can be assigned according to the rules described above. The result for each test case should be printed on its own line to standard output (stdout).

## sample

1
5
1 1 2 1 2

4

</p>