#include<stdio.h>
#include<string.h>
#define gc getchar_unlocked
#define MAXSIZE 100001
#define flip(i) arr[i]=(1+arr[i])%2+48 //macro for flipping
long int readint()
{
register long int c=gc();
register long int x=0;
for(;(c<48||c>57);c=gc());
for(;c>47&&c<58;c=gc())
{
x=(x<<1)+(x<<3)+c-48;
}
return x;
}
char arr[MAXSIZE];
long int count[MAXSIZE];
long int nreplace(char,long int);
int main(void){
long int t,n,i,k,ans1,fans,c,initial,nflip,j;
char flag,temp;
t=readint();
while(t--){
n=readint();
k=readint();
gets(arr);
if(k!=1){ //when k>1
for(i=1,c=1,count[0]=1;i<n;++i){
if(arr[i]==arr[i-1]){
++c;
count[i]=c;
}
else{
count[i]=c=1;
}
}
i=n-1;
fans=0;
while(i>=0){
if(count[i]>k){
initial=count[i]%(k+1);
if(initial==0){
++initial;
}
nflip=count[i]/(k+1);
for(j=i-initial;nflip>0;j-=(k+1),--nflip){
flip(j);
++fans;
}
}
i-=count[i];
}
printf("%ld\n",fans);
puts(arr);
}
else{ //when k==1
ans1=nreplace('0',n);
fans=nreplace('1',n);
flag='1';
if(ans1<fans){
fans=ans1;
flag='0';
}
for(temp=(1+flag)%2+48,i=0;i<n;++i){
arr[i]=flag;
++i;
if(i<n){
arr[i]=temp;
}
}
printf("%ld\n",fans);
puts(arr);
}
}
return 0;
}
long int nreplace(char flag,long int l){
long int ans=0,i;
if(flag){
for(i=0;i<l;i+=2){ //for even
if(arr[i]!='0')
++ans;
}
for(i=1;i<l;i+=2){ //for odd
if(arr[i]!='1')
++ans;
}
}
else{
for(i=0;i<l;i+=2){ //for even
if(arr[i]!='1')
++ans;
}
for(i=1;i<l;i+=2){ //for odd
if(arr[i]!='0')
++ans;
}
}
return ans;
}