Gom Đũa

Điểm: 0,10 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

vnoicup

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Có $n$ thanh tre có độ dài $a_{1}, a_{2}, \dots, a_{n}$ nguyên dương. Bạn được phép thực hiện thao tác sau không hoặc nhiều lần:

Chọn một thanh tre bất kì, bẻ thanh tre đó thành hai thanh tre nhỏ hơn có độ dài nguyên dương, sao cho hai thanh tre mới có độ dài không bằng nhau.

Sau khi thực hiện thao tác, bạn sử dụng những thanh tre để gom thành các đôi đũa. Một đôi đũa được tạo thành từ hai thanh tre có độ dài bằng nhau. Hãy tìm số lượng đôi đũa lớn nhất có thể tạo được sau khi thực hiện thao tác trên.

Input

Mỗi test gồm nhiều test case. Dòng đầu tiên chứa số lượng test case $t$ ( $1 \leq t \leq 10 000$ ). Mô tả của mỗi test case như sau.

Dòng đầu tiên chứa số nguyên $n$ ( $1 \leq n \leq 2 \cdot 10^{5}$ ) — số lượng thanh tre.

Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 10^{9}$ ) — độ dài của các thanh tre.

Dữ liệu đảm bảo rằng tổng $n$ trong tất cả các test case không quá $2 \cdot 10^{5}$ .

Output

Với mỗi test case, in ra một số nguyên duy nhất là số lượng đôi đũa lớn nhất tạo được.

Scoring

Subtask	Điểm	Ràng buộc
1	$250$	$a_{i} \leq 3$
2	$250$	Không có ràng buộc gì thêm
Tổng	$500$

Sample Input 1

Copy

2
7
1 1 1 2 2 2 2
4
2 3 3 2

Sample Output 1

Copy

3
3

Sample Input 2

Copy

2
1
4
10
3 1 4 1 5 9 2 6 5 3

Sample Output 2

Copy

1
15

Notes

Trong test case đầu tiên ở ví dụ đầu tiên, ta có $3$ thanh tre độ dài $1$ , và $4$ thanh tre độ dài $2$ . Ta không thể bẻ thanh tre nào thành hai thanh tre nhỏ hơn mà có độ dài khác nhau. Từ các thanh tre này, ta có thể tạo ra $1$ đôi đũa từ hai thanh tre độ dài $1$ , và thêm $2$ đôi đũa nữa từ các thanh tre độ dài $2$ . Như vậy số lượng đôi đũa có thể tạo được là $1 + 2 = 3$ .

Lưu ý ta còn lại một thanh tre độ dài $1$ không ghép với thanh tre nào cả.

Trong test case thứ hai ở ví dụ đầu tiên, ta có thể bẻ thanh tre có độ dài $3$ thành hai thanh tre nhỏ hơn có độ dài $1$ và $2$ . Như vậy ta sẽ có $1$ đôi đũa từ thanh tre độ dài $1$ , và $2$ đôi đũa từ thanh tre độ dài $2$ . Như vậy ta cũng vẫn thu được $1 + 2 = 3$ đôi đũa.

Trong test case đầu tiên ở ví dụ thứ hai, ta có duy nhất một thanh tre độ dài $4$ . Ban đầu ta có thể bẻ thanh tre này thành thanh tre độ dài $1$ và $3$ . Tiếp đó ta có thể bẻ thanh tre độ dài $3$ thành thanh tre độ dài $1$ và $2$ . Từ đây ta có thể tạo ra một đôi đũa từ hai thanh tre độ dài $1$ .

Bình luận

Hãy đọc nội quy trước khi bình luận.

-15

ThaoDao10tin đã bình luận 3:55:17 ch, 13/06/2024

I'm back !!!

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-33

tonblan đã bình luận 4:06:18 ch, 10/06/2024

dit me cuoc doi

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.