Đổi quà kẹo (Candy Box, hard version)

Có $n$ viên kẹo trong một hộp. Viên kẹo thứ $i$ có loại $a_i$ ($1\le a_i\le n$).

Bạn muốn chuẩn bị một hộp quà bằng cách chọn ra một số viên kẹo, với ràng buộc: số lượng kẹo của mỗi loại được đưa vào hộp quà phải đôi một khác nhau (ví dụ, một hộp quà có hai viên loại $1$ và hai viên loại $2$ là không hợp lệ).

Có thể có nhiều loại kẹo hoàn toàn không xuất hiện trong hộp quà. Cũng có thể không phải tất cả kẹo của một loại đều được lấy.

Ngoài ra, mỗi viên kẹo có một giá trị $f_i$: $f_i=0$ nghĩa là bạn muốn giữ viên đó cho riêng mình, $f_i=1$ nghĩa là bạn sẵn sàng đưa nó vào hộp quà. Hai viên kẹo cùng loại vẫn có thể có $f_i$ khác nhau.

Bạn muốn hộp quà càng lớn càng tốt, nhưng đồng thời không muốn cho đi quá nhiều viên kẹo mà bạn muốn giữ lại. Vì vậy, trước tiên hãy tối đa hoá tổng số viên kẹo trong hộp quà; sau đó, trong tất cả các cách đạt được số kẹo lớn nhất, hãy tối đa hoá số viên kẹo có $f_i=1$.

Bạn cần trả lời $q$ truy vấn độc lập.

Dữ liệu vào

• Dòng đầu chứa số nguyên $q$ là số truy vấn.
• Với mỗi truy vấn:
  • Dòng đầu chứa số nguyên $n$ là số viên kẹo.
  • $n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i$ và $f_i$ ($1\le a_i\le n$, $0\le f_i\le 1$).

Dữ liệu ra

Với mỗi truy vấn, in ra hai số nguyên trên một dòng:

• Số viên kẹo lớn nhất có thể đưa vào hộp quà.
• Số viên kẹo có $f_i=1$ lớn nhất, trong số các hộp quà đạt được số kẹo lớn nhất nói trên.

Ràng buộc

• $1\le q\le 2·{10}^5$
• $1\le n\le 2·{10}^5$
• $1\le a_i\le n$, $0\le f_i\le 1$
• Tổng $n$ trên tất cả các truy vấn không vượt quá $2·{10}^5$.

Ví dụ