Bessie tiene una cadena binaria oculta ~b_1b_2...b_N~. La única información disponible sobre ~b~ es una cadena binaria ~r_1r_2...r_{N-K+1}~, donde ~r_i~ es el resto de la división por dos del número de unos en la ventana de longitud ~K~ de ~b~ con índice ~i~ más a la izquierda.

Imprime el número mínimo y máximo posible de unos en la cadena binaria oculta de Bessie.

Entrada

Hay ~T~ casos de prueba independientes que deben resolverse. Cada prueba se especifica de la siguiente manera:

• La primera línea contiene ~N~ y ~K~.
• La segunda línea contiene la cadena binaria ~r_1...r_{N-K+1}~, donde ~r_i=\sum_{j=i}^{j+K-1}b_j\pmod{2}~.

Se garantiza que la suma de ~N~ en todas las pruebas no supera ~10^6~.

Salida

Para cada caso de prueba, imprimir el número mínimo y máximo posible de unos en la cadena binaria oculta de Bessie, separados por un espacio.

Restricciones

• ~1 \leq N \leq 2 \cdot 10^5~
• ~1 \leq K \leq N~
• ~1 \leq T \leq 10^3~

Ejemplo de Entrada

7
5 1
10011
5 2
1001
5 3
100
5 5
0
5 5
1
4 4
1
5 2
0000

Ejemplo de Salida

3 3
2 3
1 4
0 4
1 5
1 3
0 5

Para el primer caso de prueba, ~K=1~ significa que ~r=b~, y el número de unos en ~r~ es 3.

Para el segundo caso de prueba, hay dos posibilidades para ~b: 10001~ y ~01110~, con 2 y 3 unos, respectivamente.

USACO 2026 First Contest, Silver Problem 3. Sliding Window Summation.