题目描述

众所周知，观者是尖塔第四弱的职业。

观者很久之前种了一棵树，现在她想来取树枝，却发现树已经四分五裂，现在只能辨认出每个结点的度数。观者想知道，在符合要求的所有树形态中，她最多能收集多少个完整的树枝？完整的树枝包括一条边以及它对应的两个顶点，取下的不同完整树枝不能共享顶点。

形式化题意：给定树的度数序列，在所有符合要求的树中求最大匹配大小的最大值（最大匹配定义为，选择尽可能多的边使得边直接两两不公共顶点）。

输入格式

第一行一个正整数 $T$，表示询问组数。

接下来 $T$ 组数据，每组数据占两行。第一行一个正整数 $n$，第二行一个长度为 $n$ 的正整数序列表示度数序列。

输出格式

$T$ 行，每行一个非负整数，表示答案。

5
2
1 1
3
2 1 1
6
2 2 1 1 1 3
6
2 3 1 2 1 1
6
2 1 1 2 2 2

1
1
3
3
3

样例 2~4 见下发文件：样例下载。

数据范围

对于 $100\%$ 的数据，保证 $2\leqslant n\leqslant 2\times 10^5,\sum n\leqslant 4\times 10^5$，即所有数据的 $n$ 之和不超过 $4\times 10^5$。

特殊性质 A：保证存在一个点度数大于 $n-10$。

特殊性质 B：保证度数为 $1$ 的结点数量不超过 $10$ 个。