给定一棵树的度数序列（所有顶点的度数，顺序任意）。 在所有具有给定度数序列的树中，找到一棵具有最大匹配的树，并输出该最大匹配的大小。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 100\,000$)：测试用例的数量。 接下来是 $t$ 个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 200\,000$)：顶点数。 下一行包含 $n$ 个整数 $d_1, d_2, \dots, d_n$ ($1 \le d_i \le n - 1$)，即树的度数序列。 保证 $\sum d_i = 2(n - 1)$，且至少存在一棵具有给定度数序列的树。 同时保证所有测试用例中 $n$ 的总和不超过 $200\,000$。

输出格式

对于每个测试用例，输出一个整数：在所有具有给定度数序列的树中，最大匹配的最大值。

样例

样例输入 1

2
10
1 1 2 2 2 2 2 2 2 2
5
4 1 1 1 1

样例输出 1

5
1

说明

在第一个测试用例中，你可以构造一条包含 10 个顶点的路径，它具有相同的度数序列，且最大匹配尽可能大。 在第二个测试用例中，唯一可能的树是星形图（一个顶点与所有其他顶点相连），其最大匹配为 1。