B'Polycarp was given an array of a[1 ... n] of n integers. He can perform the following operation with the array a no more than n times: The two items above together denote one single operation. For example, if Polycarp has an array a = [3, 1, 6, 6, 2] , then it can perform the following sequence of operations with it: Note that Polycarp could stop performing operations at any time. Polycarp wondered how many minimum operations he would need to perform to make all the elements of a equal (i.e., he wants all a_i are equal to each other). The first line contains a single integer t ( 1 <= q t <= q 3000 ) -- the number of test cases in the test. Then t test cases follow. The first line of each test case contains a single integer n ( 1 <= q n <= q 3000 ) -- the length of the array. The next line contains n integers a_1, a_2, ldots, a_n ( 1 <= q a_i <= q 10^5 ) -- array a . It is guaranteed that the sum of n over all test cases does not exceed 3000 . For each test case, output a single number -- the minimum number of operations that Polycarp needs to perform so that all elements of the a array are the same (equal). In the first test case of the example, the answer can be constructed like this (just one way among many other ways): [3, 1, 6, 6, 2] xrightarrow[]{i=4,~add~to~left} [3, 1, 12, 2] xrightarrow[]{i=2,~add~to~right} [3, 13, 2] xrightarrow[]{i=1,~add~to~right} [16, 2] xrightarrow[]{i=2,~add~to~left} [18] . All elements of the array [18] are the same. In the second test case of the example, the answer can be constructed like this (just one way among other ways): [1, 2, 2, 1] xrightarrow[]{i=1,~add~to~right} [3, 2, 1] xrightarrow[]{i=3,~add~to~left} [3, 3] . All elements of the array [3, 3] are the same. In the third test case of the example, Poly'...