POLSKI SPOJ

Najdłuższy spójny podciąg ciągu binarnego

Jaką długość ma najdłuższy spójny podciąg ciągu binarnego zawierający co najwyżej k jedynek?

Wejście
W pierwszym wierszu znajduje się liczba d zestawów testowych (0<d<=5).
Każdy zestaw składa się z dwóch wierszy. W pierwszym wierszu dane są dwie liczby całkowite: n, k (1<n<=500000, k<=10000, k<n), gdzie liczba n oznacza długość ciągu binarnego. W wierszu drugim znajduje się ciąg binarny o długości n.

Wyjście
Na wyjściu należy wypisać d wierszy, w każdym jedna liczba będąca odpowiedzią na pytanie postawione w zadaniu.

Przykład

Wejście
3
10 1
0101000001
12 2
010110101001
15 3
101000011100100

Wyjście
7
6
9