Maximum Beauty of the Garden

You are given a garden with n flower beds arranged in a row. Each bed contains a flower of a particular type. You are allowed to rearrange the flower beds arbitrarily. The beauty of the garden is defined as the maximum number of consecutive flower beds that contain the same type of flower after an optimal rearrangement.

More formally, for each test case you are given an integer $n$ and an array $a = [a_1, a_2, \dots, a_n]$. Let $f(x)$ denote the frequency of the flower type $x$ in the array. The beauty of the garden is

Your task is to compute this value for each test case.

inputFormat

The input is read from standard input (stdin). It begins with an integer $T$ representing the number of test cases. For each test case, the first line contains an integer $n$ indicating the number of flower beds. The second line contains $n$ space-separated integers representing the types of flowers in the garden.

outputFormat

For each test case, output a single integer on a new line indicating the maximum beauty of the garden.## sample

1
5
1 2 2 3 3

2