MÀU SẮC KHÁC NHAU

Bối cảnh

Có N loại màu sắc khác nhau được đánh số từ 1 đến N. FullHouse Dev có A[i] ​viên bi có màu i, ( 1 ≤ i ≤ N ).

Yêu cầu

FullHouse Dev sẽ sắp xếp một số hộp và đặt mỗi viên bi vào một trong những hộp đó. Tìm số lượng tối thiểu các hộp FullHouse Dev cần sao cho không có hộp nào chứa hai viên bi cùng màu.

Input

Dòng đầu tiên của đầu vào chứa một số nguyên T, đại diện cho số lượng trường hợp kiểm tra. Mô tả của các trường hợp kiểm tra theo sau.

Dòng đầu tiên của mỗi trường hợp kiểm tra chứa một số nguyên N, đại diện cho số lượng màu sắc. Dòng thứ hai của mỗi trường hợp kiểm tra chứa N N số nguyên cách nhau bằng khoảng trắng A1 , A2 , … , AN ​— đại diện cho số lượng viên bi có màu i.

Output

Đối với mỗi trường hợp kiểm tra, xuất số lượng tối thiểu các hộp cần thiết sao cho không có hộp nào chứa hai viên bi cùng màu.

Ràng buộc

1 ≤ T ≤ 1000
2 ≤ N ≤ 100
1 ≤ A[i]​≤ 10^5

Ví dụ 1

Input

3
2
8 5
3
5 10 15
4
4 4 4 4

Output

8
15
4

Giải thích ví dụ

Trường hợp kiểm tra 1: FullHouse Dev cần ít nhất 8 hộp sao cho không có hộp nào chứa hai viên bi cùng màu. Một cấu hình có thể của 8 hộp là { [ 1 , 2 ] , [ 1 , 2 ] , [ 1 , 2 ] , [ 1 , 2 ] , [ 1 , 2 ] , [ 1 ] , [ 1 ] , [ 1 ] } trong đó phần tử thứ i của tập hợp này đại diện cho màu sắc của các viên bi trong hộp thứ i.

Trường hợp kiểm tra 2: FullHouse Dev cần ít nhất 15 hộp sao cho không có hộp nào chứa hai viên bi cùng màu.

Trường hợp kiểm tra 3: FullHouse Dev cần ít nhất 4 hộp sao cho không có hộp nào chứa hai viên bi cùng màu. Một cấu hình có thể của 4 hộp là { [ 1 , 2 , 3 , 4 ] , [ 1 , 2 , 3 , 4 ] , [ 1 , 2 , 3 , 4 ] , [ 1 , 2 , 3 , 4 ] } trong đó phần tử thứ i của tập hợp này đại diện cho màu sắc của các viên bi trong hộp thứ i.

Thông tin học tập

• Buổi: B04
• Concepts: for loops, maximum tracking
• Giới hạn kiến thức: B01-B04
• Time limit: 2 seconds
• Memory limit: 20 MB
• Point: 15