#include<iostream>
using namespace std;
bool k[1000000][2];
string ak,bk;
int main()
{
    int wta,wt;cin>>wta>>wt;
    while(wt--)
    {
        int a,b;
        cin>>a>>b;// a is the line,b is the times.
        cin>>ak>>bk;
        //cout<<ak<<endl<<bk<<endl;
        for(int i=1;i<=a;i++)k[i][0]=ak[i-1]-'0';
        for(int i=1;i<=a;i++)k[i][1]=bk[i-1]-'0';
        int maxx=0,times=0,ahead=0,aheadful=0,yn=0,yn0=0,yn1=0,ynt=0;//the ahead named of the times which of the score.
        /*
        yn named of Y/N check,yn0 and yn1 named of Y/N check the line 1 of line 2
        ynt的工作是记录最后一个11串的距离。
        */
        for(int i=1;i<=a;i++)
        {

            if(times<0)
            {
                yn=0;yn1=0;yn0=0;times = 0;ynt=0;ahead=0;
            }
            if(yn==0)//在没有连通块的情况下，决定是否在当前位置开始并记录01串
            {   
                if(k[i][0])
                {
                    yn = 1;
                    yn0 = 1;
                    yn1 = 0;
                    times++;
                    if(k[i][1]==0)
                    ahead++;
                    if(k[i][1]==1)
                    {times++;yn1=1;}
                    if(ynt){times-=(i-ynt);ynt=0;if(times<0){times=0;ahead=0;}}

                }
                if(k[i][1]&&!k[i][0])
                {
                    yn = 1;
                    yn0 = 0;
                    yn1 = 1;
                    times++;
                    ahead++;
                    if(ynt){times-=(i-ynt);ynt=0;if(times<0){times=0;ahead = 0;}}
                }
                            
            }
            
            else
            {
                int h=0;
                if(yn0&&!yn1)h=1;
                if(yn1&&!yn0)h=2;
                if(yn0&&yn1)h=3;
                if(h==1)
                {
                    if(k[i][0])
                    {
                        times++;
                        if(k[i][1]==1)
                        {times++;yn1=1;}
                        else {ahead++;}
                    }
                    else
                    {
                        times--;
                        if(k[i][1]==1)
                        {times++;yn1=1;}
                    }
                    
                           
                }
                if(h==2)
                {
                    if(k[i][1])
                    {
                        times++;
                        if(k[i][0]==1)
                        {times++;yn0=1;}
                        else {ahead++;}
                    }
                    else
                    {
                        times--;
                        if(k[i][0]==1)
                        {times++;yn0=1;}
                    }
                }
                if(h==3)
                {
                    if(k[i][1])
                    {
                        times++;
                        if(!k[i][0]){ahead++;yn0=0;}
                    }
                    if(k[i][0])
                    {
                        times++;
                        if(!k[i][1]){ahead++;yn1=0;}
                    }
                    if(!k[i][0]&&!k[i][1])
                    {
                        yn=0;
                        ynt = i;yn0=0;yn1=0;
                    }
                }
            }
            int kh=times;
            if(ahead<=b*2)
            {
                kh-=ahead;
            }
            else
            {
                kh-=b*2;
            }
            //maxx=max(maxx,kh);
            if(maxx<kh)
            {
                aheadful=ahead;
                maxx=kh;
            }
            //cout<<yn0<<" "<<yn1<<" " <<times<<" "<<ahead<<" "<<kh<<endl;
        }
        if(aheadful<b*2)
        {times=0;yn=0;yn1=0;yn0=0;
        for(int i=1;i<=a;i++)
        {

            if(times<0)
            {
                yn=0;yn1=0;yn0=0;times = 0;ynt=0;;
            }
            if(yn==0)//在没有连通块的情况下，决定是否在当前位置开始并记录01串
            {   
                if(!ynt)
                if(k[i][0]&&k[i][1])
                {times+=2;yn0=1;yn1=1;yn=1;}else continue;
                else
                {
                    if(k[i][0])
                    {
                        yn = 1;
                        yn0 = 1;
                        yn1 = 0;
                        times++;
                        if(k[i][1]==0)
                        times--;
                        if(k[i][1]==1)
                        {times++;yn1=1;}
                        if(ynt){times-=(i-ynt);ynt=0;if(times<0){times=0;ahead=0;}}

                    }
                    if(k[i][1]&&!k[i][0])
                    {
                        yn = 1;
                        yn0 = 0;
                        yn1 = 1;
                        times++;
                        times--;
                        if(ynt){times-=(i-ynt);ynt=0;if(times<0){times=0;ahead = 0;}}
                    }
                }
            }
        
            else
            {
                int h=0;
                if(yn0&&!yn1)h=1;
                if(yn1&&!yn0)h=2;
                if(yn0&&yn1)h=3;
                if(h==1)
                {
                    if(k[i][0])
                    {
                        times++;
                        if(k[i][1]==1)
                        {times++;yn1=1;}
                        else {times--;}
                    }
                    else
                    {
                        times--;
                        if(k[i][1]==1)
                        {times++;yn1=1;}
                    }
                    
                           
                }
                if(h==2)
                {
                    if(k[i][1])
                    {
                        times++;
                        if(k[i][0]==1)
                        {times++;yn0=1;}
                        else {times--;}
                    }
                    else
                    {
                        times--;
                        if(k[i][0]==1)
                        {times++;yn0=1;}
                    }
                }
                if(h==3)
                {
                    if(k[i][1])
                    {
                        times++;
                        if(!k[i][0]){times--;yn0=0;}
                    }
                    if(k[i][0])
                    {
                        times++;
                        if(!k[i][1]){times--;yn1=0;}
                    }
                    if(!k[i][0]&&!k[i][1])
                    {
                        yn=0;
                        ynt = i;yn0=0;yn1=0;
                    }
                }
            }
            int kh=times;
            if(maxx<kh)
            {
                aheadful=ahead;
                maxx=kh;
            }
            //cout<<yn0<<" "<<yn1<<" " <<times<<" "<<ahead<<" "<<kh<<endl;
        }
        }
        cout<<maxx<<endl;
    }
}