Ahora viene la version dificil del problema. La unica diferencia entre las dos versiones es que la version mas dificil solicita ademas un numero minimo de subsegmentos.

Davisson tiene una cadena binaria "s" de longitud "n", que consiste unicamente en "0" y "1" , donde "n" siempre sera par.

Ahora Davisson divide "s" en el numero minimo de subsegmentos contiguos, y para cada subsegmento todos los bits son iguales. Despues "s" se considera bueno si las longitudes de todos los subsegmentos son iguales.

Por Ejemplo, si "s" es "11001111", se dividira en "11", "00" y "1111". Sus longitudes son 2, 2, 4 respectivamente, que son todos numeros pares, por lo que "11001111" es bueno.

Otro Ejemplo, si "s" es "1110011000", se dividira en "111", "00", "11" y "000", y sus longitudes son 3, 2, 2, 3. Observando "1110011000" no es bueno.

Ahora Davisson quiere mejorar "s", cambiando los valores de algunas posiciones de "s".

Especificamente, puede realizar la operacion cualquier numero de veces: cambiar el valor de si a "0" o "1" (1≤i≤n).

¿Puedes decirle a Davisson el número mínimo de operaciones para hacer que "s" sea bueno? Mientras tanto, también Davisson quiere saber el número mínimo de subsegmentos en los que se puede dividir "s" entre todas las soluciones con el número mínimo de operaciones.

La primera entrada contiene un solo entero positivo t (1≤t≤10000) el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene un solo número entero n (2≤n≤2⋅10⁵)  la longitud de "s", se garantiza que "n" siempre es par.

La segunda línea contiene una cadena binaria "s" de longitud "n", que consta solo de ceros y unos.

Se garantiza que la suma de n sobre todos los casos de prueba no exceda 2⋅10⁵.

Para cada caso de prueba, imprima en una sola línea con dos enteros: el número mínimo de operaciones para hacer que "s" sea bueno y el número mínimo de subsegmentos en los que "s" se puede dividir entre todas las soluciones con el número mínimo de operaciones.