아이콘 정리하기

BerPhone X는 $n$개의 애플리케이션이 미리 설치된 채로 출시를 앞두고 있다. 애플리케이션의 카테고리는 이 애플리케이션의 장르나 주제를 나타낸다(예: "게임", "비즈니스", "교육"). 카테고리는 $1$ 이상 $n$ 이하의 정수로 주어지며, $i$번째 애플리케이션의 카테고리는 $c\_i$이다.

화면의 개수 $m$과 각 화면의 크기 $s$를 정할 수 있다. 다음 조건을 만족하도록 $n$개 애플리케이션의 아이콘(애플리케이션 하나당 아이콘 하나)을 모두 배치해야 한다.

• 각 화면에서 모든 아이콘은 같은 카테고리의 애플리케이션에 속해야 한다(서로 다른 화면이 같은 카테고리 애플리케이션의 아이콘을 담아도 된다).
• 각 화면은 아이콘으로 완전히 채워지거나(화면에 있는 아이콘의 수가 $s$와 같다), 거의 채워져야 한다(아이콘의 수가 $s-1$과 같다).

가능한 화면 개수 $m$의 최솟값을 구하라.

첫째 줄에 정수 $t$ ($1 \le t \le 10\,000$)가 주어진다. 이는 입력에 있는 테스트 케이스의 수이다. 그다음 $t$개의 테스트 케이스가 이어진다.

각 테스트 케이스의 첫째 줄에 정수 $n$ ($1 \le n \le 2\cdot10^6$)이 주어진다. 이는 아이콘의 수이다. 둘째 줄에 $n$개의 정수 $c\_1, c\_2, \dots, c\_n$ ($1 \le c\_i \le n$)이 주어지며, $c\_i$는 $i$번째 애플리케이션의 카테고리이다.

입력에 있는 모든 테스트 케이스의 $n$ 값의 합은 $2\cdot10^6$을 넘지 않는다.

$t$개의 정수를 출력한다. 이는 입력에 나온 순서대로 각 테스트 케이스의 답이다. 테스트 케이스의 답은 주어진 조건을 만족하도록 $n$개의 아이콘을 모두 배치할 수 있는 최소 화면 개수 $m$이다.

예제의 첫 번째 테스트 케이스에서는 모든 아이콘을 크기 $4$인 세 화면에 배치할 수 있다. 카테고리 $1$의 아이콘 $4$개가 있는 화면, 카테고리 $1$의 아이콘 $3$개가 있는 화면, 카테고리 $5$의 아이콘 $4$개가 있는 화면이다.