Question
Find the Largest K
Naina is given an array A of size N. Find the largest integer K such that there exists a subsequence S of length K where K is divisible by the number of distinct elements in S.
Input
The first line contains a single integer T, denoting the number of test cases.
The first line of each test case contains a positive integer N, the length of array A.
The second line contains N space-separated integers, A1, A2, ..., AN - denoting the array A.
Constraints
1 ≤ T ≤ 104
1 ≤ A i ≤ N ≤ 2x105
The sum of N over all test cases won't exceed 2x105
The first line of each test case contains a positive integer N, the length of array A.
The second line contains N space-separated integers, A1, A2, ..., AN - denoting the array A.
Constraints
1 ≤ T ≤ 104
1 ≤ A i ≤ N ≤ 2x105
The sum of N over all test cases won't exceed 2x105
Output
For each test case, output the largest valid K.
Example
Input
2
2
2 1
4
1 2 1 3
Output
2
3
Explanation
Test case 1: Consider the subsequence [2, 1] consisting of 2 distinct elements. The length of subsequence is 2 which is divisible by the number of distinct elements.
Test case 2:Consider the subsequence [2, 1, 3] consisting of 3 distinct elements. The length of subsequence is 3 which is divisible by the number of distinct elements.
2
2
2 1
4
1 2 1 3
Output
2
3
Explanation
Test case 1: Consider the subsequence [2, 1] consisting of 2 distinct elements. The length of subsequence is 2 which is divisible by the number of distinct elements.
Test case 2:Consider the subsequence [2, 1, 3] consisting of 3 distinct elements. The length of subsequence is 3 which is divisible by the number of distinct elements.