給定一棵樹的度數序列（所有頂點的度數，順序任意）。 在所有具有給定度數序列的樹中，找出具有最大匹配（maximum matching）的樹，並輸出該最大匹配的大小。

輸入格式

第一行包含一個整數 $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$。