#include<stdio.h>
int main()
{
long long int t,n,k,i,j,count,c,flag,c1,c2;
while(t--)
{
c=0;
c1=0;
c2=0;
count=0;
char a[n+1];
char b[n+1];
for(i=0;i<n;i++)
b[i]=a[i];
if(k>1)
{
i=0;
count=0;
while(i<n-1)
{
count=0;
while(a[i]==a[i+1])
{
count++;
if(count>k)
{
c++;
if(a[i]=='0')
a[i]='1';
else
a[i]='0';
count=0;
}
i++;
}
count++;
if(count>k)
{
c++;
if(a[i-1]=='0')
a[i-1]='1';
else
a[i-1]='0';
count=0;
}
i++;
}
if(a[n-1]==a[n])
{
count++;
if(count>k)
{
c++;
if(a[n-1]=='0')
a[n-1]='1';
else
a[n-1]='0';
count=0;
}
}
for(i=0;i<n;i++)
}
else
{
i=0;
while(i<n-1)
{
if(a[i]==a[i+1])
{
count++;
if(a[i+1]=='0')
a[i+1]='1';
else
a[i+1]='0';
c1++;
}
i++;
}
i=n-1;
while(i>0)
{
if(b[i]==b[i-1])
{
if(b[i-1]=='0')
b[i-1]='1';
else
b[i-1]='0';
c2++;
}
i--;
}
if(c1<=c2)
{
for(i=0;i<n;i++)
}
else
{
for(i=0;i<n;i++)
}
}
}
return 0;
}
ICNpbmNsdWRlPHN0ZGlvLmg+CiAgICBpbnQgbWFpbigpCiAgICB7CiAgICAJbG9uZyBsb25nIGludCB0LG4sayxpLGosY291bnQsYyxmbGFnLGMxLGMyOwogICAgCXNjYW5mKCIlbGxkIiwmdCk7CiAgICAJd2hpbGUodC0tKQogICAgCXsKICAgIAkJYz0wOwogICAgCQljMT0wOwogICAgCQljMj0wOwogICAgCQljb3VudD0wOwogICAgCQlzY2FuZigiJWxsZCVsbGQiLCZuLCZrKTsKICAgIAkJY2hhciBhW24rMV07CiAgICAJCWNoYXIgYltuKzFdOwogICAgCQlzY2FuZigiJXMiLCZhKTsKICAgIAkJZm9yKGk9MDtpPG47aSsrKQogICAgCQliW2ldPWFbaV07CiAgICAJCWlmKGs+MSkKICAgIAkJewogICAgCQkJaT0wOwogICAgCQkJY291bnQ9MDsKICAgIAkJCXdoaWxlKGk8bi0xKQogICAgCQkJewogICAgCQkJCWNvdW50PTA7CiAgICAJCQkJd2hpbGUoYVtpXT09YVtpKzFdKQogICAgCQkJCXsKICAgIAkJCQkJY291bnQrKzsKICAgIAkJCQkJaWYoY291bnQ+aykKICAgIAkJCQkJewogICAgCQkJCQkJYysrOwogICAgCQkJCQkJaWYoYVtpXT09JzAnKQogICAgCQkJCQkJYVtpXT0nMSc7CiAgICAJCQkJCQllbHNlCiAgICAJCQkJCQlhW2ldPScwJzsKICAgIAkJCQkJCWNvdW50PTA7CiAgICAJCQkJCX0KICAgIAkJCQkJaSsrOwogICAgCQkJCX0KICAgIAkJCQljb3VudCsrOwogICAgCQkJCWlmKGNvdW50PmspCiAgICAJCQkJCXsKICAgIAkJCQkJCWMrKzsKICAgIAkJCQkJCWlmKGFbaS0xXT09JzAnKQogICAgCQkJCQkJYVtpLTFdPScxJzsKICAgIAkJCQkJCWVsc2UKICAgIAkJCQkJCWFbaS0xXT0nMCc7CiAgICAJCQkJCQljb3VudD0wOwogICAgCQkJCQl9CiAgICAJCQkJCWkrKzsKICAgIAkJCX0KICAgIAkJCWlmKGFbbi0xXT09YVtuXSkKICAgIAkJCXsKICAgIAkJCWNvdW50Kys7CiAgICAJCQlpZihjb3VudD5rKQogICAgCQkJCQl7CiAgICAJCQkJCQljKys7CiAgICAJCQkJCQlpZihhW24tMV09PScwJykKICAgIAkJCQkJCWFbbi0xXT0nMSc7CiAgICAJCQkJCQllbHNlCiAgICAJCQkJCQlhW24tMV09JzAnOwogICAgCQkJCQkJY291bnQ9MDsKICAgIAkJCQkJfQogICAgCQl9CgkJICAgIHByaW50ZigiJWxsZFxuIixjKTsKCQkJZm9yKGk9MDtpPG47aSsrKQoJCQlwcmludGYoIiVjIixhW2ldKTsKCQkJcHJpbnRmKCJcbiIpOwogICAgfQogICAgZWxzZQogICAgewogICAgCWk9MDsKICAgIHdoaWxlKGk8bi0xKQogICAgewogICAgCWlmKGFbaV09PWFbaSsxXSkKICAgIAl7CiAgICAJCWNvdW50Kys7CiAgICAJCWlmKGFbaSsxXT09JzAnKQogICAgCQlhW2krMV09JzEnOwogICAgCQllbHNlCiAgICAJCWFbaSsxXT0nMCc7CiAgICAJCWMxKys7CiAgICAJfQogICAgCWkrKzsKICAgIH0KICAgIGk9bi0xOwogICAgd2hpbGUoaT4wKQogICAgewogICAgCWlmKGJbaV09PWJbaS0xXSkKICAgIAl7CiAgICAJCWlmKGJbaS0xXT09JzAnKQogICAgCQliW2ktMV09JzEnOwogICAgCQllbHNlCiAgICAJCWJbaS0xXT0nMCc7CiAgICAJCWMyKys7CiAgICAJfQogICAgCWktLTsKICAgIH0KICAgIGlmKGMxPD1jMikJCQogewogICAgcHJpbnRmKCIlbGxkXG4iLGMxKTsKICAgIGZvcihpPTA7aTxuO2krKykKCXByaW50ZigiJWMiLGFbaV0pOwoJcHJpbnRmKCJcbiIpOwp9CiAgICBlbHNlCiB7CiAgICBwcmludGYoIiVsbGRcbiIsYzIpOwogICAgZm9yKGk9MDtpPG47aSsrKQoJcHJpbnRmKCIlYyIsYltpXSk7CglwcmludGYoIlxuIik7Cn0KICAgIH0KICAgIAl9CiAgICByZXR1cm4gMDsKICAgIH0gICAKICA=