There are ~n~ bamboo sticks with lengths ~a_1, a_2, \ldots, a_n~ as positive integers. You are allowed to perform the following operation zero or multiple times:

- Choose any stick, break it into two smaller sticks with positive
integer lengths, such that the two new sticks have
**unequal lengths**.

After performing the operation, you use the sticks to form pairs of
chopsticks. A pair of chopsticks is formed from two sticks with **equal
lengths**. Find the maximum number of pairs of chopsticks that can be
formed after performing the operation.

#### Input

The input consists of multiple test cases. The first line of the input contains a positive integer ~t~ (~1 \le t \le 10\,000~) which is the number of test cases. The description of each test case is as follows.

The first line contains an integer ~n~ (~1 \le n \le 2 \cdot 10^5~) — the number of bamboo sticks.

The second line contains ~n~ integers ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^9~) — the lengths of the bamboo sticks.

The sum of ~n~ in all test cases is guaranteed not to exceed ~2 \cdot 10^5~.

#### Output

For each test case, output a single integer denoting the **maximum**
number of pairs of chopsticks that can be formed.

#### Scoring

Subtask |
Score |
Constraints |
---|---|---|

1 | ~250~ | ~a_i \le 3~ |

2 | ~250~ | No additional constraints |

Total | ~500~ |

#### Sample Input 1

```
2
7
1 1 1 2 2 2 2
4
2 3 3 2
```

#### Sample Output 1

```
3
3
```

#### Sample Input 2

```
2
1
4
10
3 1 4 1 5 9 2 6 5 3
```

#### Sample Output 2

```
1
15
```

#### Notes

In the first test case in the first example, we have ~3~ bamboo sticks of length ~1~, and ~4~ bamboo sticks of length ~2~. We cannot break any stick into two smaller sticks with different lengths. From these sticks, we can create ~1~ pair of chopsticks from two sticks of length ~1~, and add ~2~ more pairs from the sticks of length ~2~. Thus, the maximum number of pairs of chopsticks that can be formed is ~1 + 2 = 3~.

Note that there is one stick of length ~1~ left unused.

In the second test case in the first example, we can break the stick of length ~3~ into two smaller sticks of length ~1~ and ~2~. Thus, we will have ~1~ pair of chopsticks from the stick of length ~1~, and ~2~ pairs from the stick of length ~2~. Therefore, we still obtain ~1 + 2 = 3~ pairs of chopsticks.

In the first test case in the second example, we have only one bamboo stick of length ~4~. Initially, we can break this stick into sticks of length ~1~ and ~3~. Then we can break the stick of length ~3~ into sticks of length ~1~ and ~2~. From here, we can create a pair of chopsticks from two sticks of length ~1~.

## Comments

This comment is hidden due to too much negative feedback. Show it anyway.

This comment is hidden due to too much negative feedback. Show it anyway.