#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
using namespace std;
inline int read() {
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
typedef long long ll;
int f[110][110][55][3];
char s[110],s2[110];
int p2[110][110],p3[110][110],cnt2,cnt3;
int dis(int i,int j) {return abs(i-j);}
void solve() {
    int n=read(),m=read();m/=2;
    scanf("%s",s+1);
    cnt2=cnt3=0;
    rep(i,1,n) {
        if(s[i]=='2') cnt2++;
        else cnt3++;
    }
    rep(i,0,n-1) rep(j,0,i) {
        if(j>cnt2||i-j>cnt3) continue;
        rep(k,1,n) s2[k]=s[k];
        rep(k,1,j) {
            rep(t,k,n) if(s2[t]=='2') {swap(s2[t],s2[k]);break;}
        }
        rep(k,j+1,i) {
            rep(t,k,n) if(s2[t]=='3') {swap(s2[t],s2[k]);break;}
        }
        rep(k,i+1,n) if(s2[k]=='2') {p2[i][j]=k;break;}
        rep(k,i+1,n) if(s2[k]=='3') {p3[i][j]=k;break;}
        //printf("%d %d %d %d\n",i,j,p2[i][j],p3[i][j]);
    }
    rep(i,0,n) rep(j,0,n) rep(k,0,m) rep(d,0,2) f[i][j][k][d]=-n;
    f[0][0][0][2]=0;
    rep(i,0,n-1) rep(j,0,i) rep(k,0,m) rep(d,0,2) {
        if(j>cnt2||i-j>cnt3) continue;
        int ans=f[i][j][k][d];
        if(k+dis(p2[i][j],i+1)<=m) f[i+1][j+1][k+dis(p2[i][j],i+1)][0]=max(f[i+1][j+1][k][0],ans);
        if(k+dis(p3[i][j],i+1)<=m) {
            if(d==1) f[i+1][j][k+dis(p3[i][j],i+1)][2]=max(f[i+1][j][k+dis(p3[i][j],i+1)][2],ans+1);
            else f[i+1][j][k+dis(p3[i][j],i+1)][min(2,d+1)]=max(f[i+1][j][k+dis(p3[i][j],i+1)][min(2,d+1)],ans);
        }
    }
    int ans=0;
    rep(k,0,m) rep(d,0,2) ans=max(ans,f[n][cnt2][k][d]);
    printf("%d\n",ans);
}
int main() {
    dwn(T,read(),1) solve();
    return 0;
}
/*
4
5 0
23233
9 0
232332333
9 2
232332333
9 4
232332333
*/