Để giải bài toán này, ta sử dụng phương pháp tham lam. Cách để gom được các đôi đũa một cách tối ưu là ta nên bẻ các thanh tre thành các thanh tre độ dài ~1~ và ~2~. Cụ thể từ thanh tre ~x > 2~, tại mỗi bước ta bẻ nó thành thanh tre độ dài ~1~ và ~x - 1~. Nêu làm như vậy, đến cuối cùng ta có thể bẻ nó thành ~x - 2~ thanh tre có độ dài ~1~ và một thanh tre có độ dài ~2~. Nếu gọi ~cnt_1~ và ~cnt_2~ lần lượt là số lượng thanh tre độ dài ~1~ và ~2~ sau quá trình bẻ, vậy đáp án sẽ là ~\lfloor cnt_1 / 2 \rfloor + \lfloor cnt_2 / 2\rfloor~.

Đây là cách làm tối ưu. Thật vậy, nếu ta có một đôi đũa làm từ hai thanh tre độ dài ~x > 2~, ta luôn có thể tăng số lượng đôi đũa này lên một bằng cách bẻ thanh tre để tạo thành một đôi đũa từ hai thanh tre độ dài ~(x - 1)~ và một đôi khác từ hai thanh tre độ dài ~1~.

ntest = int(input())
for _ in range(ntest):
    n = int(input())
    a = map(int, input().split())
    cnt1, cnt2 = 0, 0
    for x in a:
        if x == 1:
            cnt1 += 1
        else:
            cnt2 += 1
            cnt1 += x - 2
    print(cnt1 // 2 + cnt2 // 2)