Bessie la vaca estaba contenta del regreso reciente a clases presenciales. Desafortunadamente, su instructor, el Granjero Juan, dicta clases muy aburridas, y por lo tanto ella frecuentemente se queda dormida en clases. El Granjero Juan se ha dado cuenta que Bessie no ha estado prestando atencion en clase. Le ha pedido a otra estudiante en clase, Elsie, llevar registro del número de veces en que Bessie se queda dormida en una clase dada. Hay ~N~ periodos de clase ~(1 \leq N \leq 10^5)~, y Elsie anota que Bessie se ha quedado dormida ~a_i~ veces ~(0 \leq ~a_i~ \leq 10^6)~ en el periodo i ésimo. Elsie, sintiéndose muy competetiva con Bessie, quiere que el Granjero Juan sienta que Bessie se está quedando dormida consistentemente el mismo número de veces en cada clase haciendo parecer que el asunto es completamente culpa de Bessie, sin depedencia de las clases algunas veces aburridas del Granjero Juan. La única manera en que Elsie puede modificar el registo es combinando dos periodos de clases adyacentes. Por ejemplo, si ~a=[1,2,3,4,5]~, entonces si Elsie combina los periodos de clases segundo y tercero, el registro se volverá ~[1,5,4,5]~.

Ayude a Elsie a calcular el número mínimo de modificaciones en el registro que necesita hacer de manera que pueda hacer que todos los números en el registro sean iguales.

Entrada

La primera línea contiene T, el número de casos de prueba a resolver. Siguen los T casos de prueba, cada uno descrito por un par de líneas. La primera línea de cada par contiene ~N~, y la segunda contiene ~a_1~, ~a_2~, ... ,~a_N~

Salida

Escriba T líneas de salida, dando el número mínimo de modificaciones que Elsie puede ejecutar para hacer que todas las entradas del registro sean iguales para cada caso.

Ejemplo de Entrada

3
6
1 2 3 1 1 1
3
2 2 3
5
0 0 0 0 0

Ejemplo de Salida

3
2
0

Para el primer caso de prueba en este ejemplo, Elsie puede cambiar su registro para que solo tenga 3s con 3 modificaciones.

1 2 3 1 1 1
3 3 1 1 1
3 3 2 1
3 3 3

Para el segundo caso, Elsie puede cambiar su registro a 7 con dos moficaciones.

2 2 3
2 5
7

Para el ultimo caso de prueba, Elsie no necesita ejecutar ninguna operacion; el registro ya consiste de entradas iguales.