木の次数列（すべての頂点の次数、順序は任意）が与えられる。 与えられた次数列を持つすべての木の中で、最大マッチングのサイズが最大となるような木を見つけよ。

入力

入力の最初の行には、テストケースの数 $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)$ であり、与えられた次数列を持つ木が少なくとも1つ存在することが保証されている。 また、すべてのテストケースにおける $n$ の総和は $200\,000$ 以下であることが保証されている。

出力

各テストケースについて、与えられた次数列を持つ木の中で最大マッチングのサイズが最大となるものを求め、その値を1行に出力せよ。

入出力例

入力 1

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

出力 1

5
1

注記

最初のテストケースでは、10個の頂点を持つパス（道）を構成することができる。これは同じ次数列を持ち、最大マッチングのサイズが最大となる。 2番目のテストケースでは、可能な木はスターグラフ（1つの頂点が他のすべての頂点と接続されているもの）のみであり、その最大マッチングのサイズは 1 である。