#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>

using namespace std;

const int INF=0x3f3f3f3f;

int N,M;
char s[103];
int rem3[103],rcou;

int dp[103][103][103][4];

int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    int T;
    scanf("%d",&T);

    while(T--) {
        scanf("%d %d",&N,&M);
        scanf("%s",s+1);
        M>>=1;
        rcou=0;
        for(int i=1;i<=N;++i) if(s[i]=='3') rem3[++rcou]=i;

        if(rcou<=1) {
            puts("0");
            continue;
        }

        for(int i=0;i<=N;++i)
            for(int j=0;j<=rcou;++j)        // use 3.
                for(int k=0;k<=M;++k)        // change num.
                    for(int sta=0;sta<4;++sta)
                        dp[i][j][k][sta]=-INF;

        dp[2][0][0][0]=0;
        dp[2][1][abs(rem3[1]-2)][1]=0;
        dp[2][1][abs(rem3[1]-1)][2]=0;
        dp[2][2][abs(rem3[1]-1)+abs(rem3[2]-2)][3]=0;

        for(int i=3;i<=N;++i)
            for(int j=0;j<=rcou;++j)
                for(int k=0;k<=M;++k)
                    for(int sta=0;sta<4;++sta)
                        if(j && k>=abs(rem3[j]-i)) {
                            dp[i][j][k][(sta&1)<<1]=max(dp[i][j][k][(sta&1)<<1],dp[i-1][j][k][sta]);
                            dp[i][j][k][((sta&1)<<1)|1]=max(dp[i][j][k][((sta&1)<<1)|1],dp[i-1][j-1][k-abs(rem3[j]-i)][sta]+((sta==1) ? 1 : 0));

                        }
                        else {
                            dp[i][j][k][((sta&1)<<1)]=max(dp[i][j][k][((sta&1)<<1)],dp[i-1][j][k][sta]);
                        }

        int ans=0;
        for(int k=0;k<=M;++k)
            for(int sta=0;sta<4;++sta)
                ans=max(ans,dp[N][rcou][k][sta]);

        printf("%d\n",ans);
    }

    return 0;
}