C++ :

#include<cstdio>
#include<cstring>
struct big
{
       int len;
       int x[205];
}P[201],A;
const big one={1,1};
const big zero={1,0};
char s1[205],s2[205];
int m,y;
int gmax(int x,int y)
{
    return x>y?x:y;
}
big operator+(big a,big b)
{
    big c;
    int i;
    memset(c.x,0,sizeof(c.x));
    c.len=gmax(a.len,b.len);
    for (i=0;i<=c.len-1;i++) c.x[i]=a.x[i]+b.x[i];
    for (i=0;i<=c.len-1;i++)
    {
        c.x[i+1]+=c.x[i]/2; c.x[i]%=2;
    }
    if (c.x[c.len]!=0) c.len++;
    return c;
}
big operator-(big a,big b)
{
    big c;
    int i;
    memset(c.x,0,sizeof(c.x));
    c.len=a.len;
    for (i=0;i<=c.len-1;i++) c.x[i]=a.x[i]-b.x[i];
    for (i=0;i<=c.len-1;i++)
        if (c.x[i]<0)
        {
           c.x[i+1]--; c.x[i]+=2;
        }
    while ((c.len>1)&&(c.x[c.len-1]==0)) c.len--;
    return c;
}
big operator*(big a,int b)
{
    big c;
    int i;
    c.len=a.len;
    memset(c.x,0,sizeof(c.x));
    for (i=0;i<=c.len-1;i++) c.x[i]=a.x[i]*b;
    for (i=0;i<=c.len-1;i++)
    {
        c.x[i+1]+=c.x[i]/2; c.x[i]%=2;
    }
    while (c.x[c.len]!=0)
    {
          c.len++; c.x[c.len]+=c.x[c.len-1]/2; c.x[c.len-1]%=2;
    }
    return c;
}
void print(big a)
{
     int i;
     for (i=a.len-1;i>=0;i--) printf("%d",a.x[i]);
     printf("\n");
}
big calc(char s[205])
{
    big A;
    int i,X;
    if ((m%2)^y) A=one;
    else A=zero;
    X=-1;
    for (i=0;i<=m-1;i++)
        if (s[i]=='1')
        {
           X=i; break;
        }
    if (X==-1) return A;
    if (((m%2)^y)==0) A=A+one;
    for (i=m-2;i>=X+1;i--)
        if (((i%2)^y)==0) A=A+P[m-1-i];
    if ((X<m-1)&&(((X%2)^y)==0))
    {
       A=A+one;
       for (i=X+1;i<=m-1;i++)
           if (s[i]=='1') A=A+P[m-1-i];
    }
    return A;
}
int main()
{
    int T,i;
   // freopen("count.in","r",stdin);
   // freopen("count.out","w",stdout);
    P[0]=one;
    for (i=1;i<=200;i++) P[i]=P[i-1]*2;
    scanf("%d",&T);
    while (T--)
    {
          scanf("%d%d%s%s",&m,&y,s1,s2);
          A=calc(s2)-calc(s1);
          for (i=m-1;i>=1;i--)
              if ((s1[i]=='0')&&(s1[i-1]=='0')) s1[i-1]='1';
              else s1[i-1]='0';
          if (s1[0]==y+'0') A=A+one;
          print(A);
    }
    return 0;
}