Davisson tiene una cadena Binaria "s" de longitud "n", que consta solo de ceros y unos, "n" es par.

Ahora Davisson divide "s" en el número mínimo de subsegmentos contiguos, y para cada subsegmento, todos los bits de cada subsegmento son iguales. Después de eso, "s" se considera bueno si las longitudes de todos los subsegmentos son iguales.

Por ejemplo, si "s" es "11001111", se dividirá en "11", "00" y "1111". Sus longitudes son 2, 2, 4 respectivamente, que son todos números pares, por lo que "11001111" es bueno. Otro ejemplo, si "s" es "1110011000", se dividirá en "111", "00", "11" y "000", y sus longitudes son 3, 2, 2, 3. Obviamente, "1110011000" no es bueno.

Davisson quiere mejorar "s" cambiando los valores de algunas posiciones en "s". Específicamente, puede realizar la operacion cualquier numero de veces: cambiar el valor de s[i] a '0' o '1'(1≤i≤n).

Ayuda a Davisson a encontrar el numero minimo de operaciones para hacer "s" bueno.

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 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 el número mínimo de operaciones para hacer "s" bueno.