Bạn được cho dãy bậc của một cây (bậc của tất cả các đỉnh, theo thứ tự bất kỳ). Trong tất cả các cây có dãy bậc đã cho, hãy tìm một cây có kích thước bộ ghép cặp cực đại lớn nhất.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên $t$ ($1 \le t \le 100\,000$): số lượng bộ dữ liệu kiểm tra. Các dòng tiếp theo chứa $t$ mô tả của các bộ dữ liệu kiểm tra. Dòng đầu tiên của mỗi bộ dữ liệu kiểm tra chứa một số nguyên $n$ ($2 \le n \le 200\,000$): số lượng đỉnh. Dòng tiếp theo chứa $n$ số nguyên $d_1, d_2, \dots, d_n$ ($1 \le d_i \le n - 1$), dãy bậc của một cây. Đảm bảo rằng $\sum d_i = 2(n - 1)$ và tồn tại ít nhất một cây với dãy bậc đã cho. Ngoài ra, đảm bảo rằng tổng của $n$ trong tất cả các bộ dữ liệu kiểm tra không vượt quá $200\,000$.

Dữ liệu ra

Với mỗi bộ dữ liệu kiểm tra, in ra một số nguyên: kích thước bộ ghép cặp cực đại lớn nhất trong số tất cả các cây có dãy bậc đã cho.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

5
1

Ghi chú

Trong bộ dữ liệu kiểm tra đầu tiên, bạn có thể xây dựng một đường thẳng với 10 đỉnh, nó sẽ có cùng dãy bậc và kích thước bộ ghép cặp cực đại lớn nhất có thể. Trong bộ dữ liệu kiểm tra thứ hai, cây duy nhất có thể là một ngôi sao (một đỉnh được nối với tất cả các đỉnh còn lại), và bộ ghép cặp lớn nhất cho nó là 1.