#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        string s;
        cin>>s;
        int ans=count(s.begin(),s.end(),'1');
        ans=max(ans,n-k);
        cout<<ans<<"\n";
    }
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        string s;
        cin>>s;
        ll ind1=-1,ind2=-1;
        for(ll i=0;i<n;i++){
            if(s[i]=='0') ind2=i;
        }
        for(ll i=n-1;i>=0;i--){
            if(s[i]=='0') ind1=i;
        }
        ll cnt=count(s.begin(),s.end(),'1');
        for(ll k=1;k<=(n/2);k++){
            if(cnt>=(n-k)) cout<<"0 ";
            else{
                ll l=ind1,r=ind2;
                r-=k;
                cout<<(r-l+k)/k<<" ";
            }
        }
        cout<<"\n";
    }
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        for(ll i=0;i<n;i++) cout<<i+1<<" ";
        cout<<"\n";
    }
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

ll mod=1e9+7;
const ll N=3e5+11;
vector<ll> v;
 
int main(){
    fast;
    v.resize(N);
    v[1]=1;
    v[2]=2;
    ll val=3,diff=3;
    for(ll i=3;i<N;i+=2){
        v[i]=(v[i-1]*(val%mod))%mod;
        v[i+1]=(v[i]*2)%mod;
        val+=diff;
        diff++;
    }
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        cout<<v[n]<<"\n";
    }
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
ll mod=1e9+7;
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll m,n;
        cin>>m>>n;
        string s;
        cin>>s;
        if(m>n) cout<<"0\n";
        else{
            vector<ll> dp(n+1);
            dp[0]=1;
            for(ll i=0;i<n;i++){
                vector<ll> ndp(n+1);
                for(ll j=0;j<=i;j++){
                    ndp[j+1]=(ndp[j+1]+dp[j])%mod;
                    if(j>0) ndp[j-1]=(ndp[j-1]+(26*dp[j])%mod)%mod;
                    else ndp[j]=(ndp[j]+dp[j])%mod;
                }
                dp=ndp;
            }
            cout<<dp[m]<<"\n";
        }
    }
}

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
//#define int long long
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=1000000001;
const int B=3000;//100;
int T,n,q;
int a[N],bnum[N];

/*
struct cmp1 	//自定义升序
{
    bool operator()(pair<int,int> v1,pair<int,int> v2)
    {
        return v1.first < v2.first;
    }
};

struct cmp2 	//自定义降序
{
    bool operator()(pair<int,int> v1,pair<int,int> v2)
    {
        return v1.first > v2.first;
    }
};
*/

struct block
{
    set<pair<int,int> >    S;
    unordered_map<int,int> cnt;
}blk[N];

void init()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n+4;i++)
    {
        blk[i].S.clear();
        blk[i].cnt.clear();
    }
    for(int i=1;i<=n;i++)
    {
        bnum[i]=i/B+1;
        blk[bnum[i]].S.insert(make_pair(a[i],i));
        blk[bnum[i]].cnt[a[i]]++;
    }
}

void solve()
{
    for(int i=1;i<=q;i++)
    {
        int t;
        cin>>t;
        if(t==1)
        {
            int l,r,x,mxl=-INF,cl=0,mnr=INF,cr=0; //l:<x,r:>=x
            cin>>l>>r>>x;
            if(bnum[l]==bnum[r])
            {
                for(int i=l;i<=r;i++)
                {
                    if(a[i]<x)
                    {
                        if(a[i]>mxl) mxl=a[i],cl=1;
                        else if(a[i]==mxl) cl++;
                    }
                    else
                    {
                        if(a[i]<mnr) mnr=a[i],cr=1;
                        else if(a[i]==mnr) cr++;
                    }
                }
            }
            else
            {
                for(int i=l;bnum[i]==bnum[l];i++)
                {
                    if(a[i]<x)
                    {
                        if(a[i]>mxl) mxl=a[i],cl=1;
                        else if(a[i]==mxl) cl++;
                    }
                    else
                    {
                        if(a[i]<mnr) mnr=a[i],cr=1;
                        else if(a[i]==mnr) cr++;
                    }
                }
                for(int i=r;bnum[i]==bnum[r];i--)
                {
                    if(a[i]<x)
                    {
                        if(a[i]>mxl) mxl=a[i],cl=1;
                        else if(a[i]==mxl) cl++;
                    }
                    else
                    {
                        if(a[i]<mnr) mnr=a[i],cr=1;
                        else if(a[i]==mnr) cr++;
                    }
                }
                for(int i=bnum[l]+1;i<=bnum[r]-1;i++)
                {
                    set<pair<int,int> >::iterator it=blk[i].S.lower_bound(make_pair(x,0));
                    if(it!=blk[i].S.end())
                    {
                        if(it->first<mnr) mnr=it->first,cr=blk[i].cnt[it->first];
                        else if(it->first==mnr) cr+=blk[i].cnt[it->first];
                    }
                    if(it==blk[i].S.begin()) continue;
                    it--;
                    if(it->first>mxl) mxl=it->first,cl=blk[i].cnt[it->first];
                    else if(it->first==mxl) cl+=blk[i].cnt[it->first];
                }
            }
            //
            //cout<<"mxl="<<mxl<<" mnr="<<mnr<<'\n';
            //
            if(mxl==-INF) cout<<cr<<'\n';
            else if(mnr==INF) cout<<cl<<'\n';
            else if(x-mxl==mnr-x) cout<<cl+cr<<'\n';
            else if(x-mxl<mnr-x) cout<<cl<<'\n';
            else cout<<cr<<'\n';
        }
        else
        {
            int p,v;
            cin>>p>>v;
            blk[bnum[p]].S.erase(make_pair(a[p],p));
            blk[bnum[p]].cnt[a[p]]--;
            a[p]=v;
            blk[bnum[p]].S.insert(make_pair(a[p],p));
            blk[bnum[p]].cnt[a[p]]++;
        }
    }
}

//-------------------------------------------------------

void gen_data()
{
    srand(time(NULL));
}

int bruteforce()
{
    return 0;
}

//-------------------------------------------------------

signed main()
{
    fastio;

	cin>>T;
	while(T--)
	{
		init();
		solve();

		/*

		//Stress Test

		gen_data();
		auto ans1=solve(),ans2=bruteforce();
		if(ans1==ans2) printf("OK!\n");
		else
		{
			//Output Data
 		}

		*/
	}

	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
ll n;
vector<ll> a;
vector<vector<ll>> adj;

vector<pair<ll,ll>> dfs(ll x, ll p){
    vector<pair<ll,ll>> dp;
    dp.push_back({0,1e18});
    for(auto i:adj[x]){
        if(i!=p){
            vector<pair<ll,ll>> ndp=dfs(i,x);
            ll n1=(ll)ndp.size();
            ndp.push_back({1e18,1e18});
            for(ll j=n1-1;j>=0;j--){
                if(ndp[j].first<1e18 || ndp[j].second<0){
                    ndp[j+1].first=min((ll)0,ndp[j+1].first);
                }
            }
            ll n2=(ll)dp.size()-1;
            vector<pair<ll,ll>> udp(n1+n2+1,{1e18,1e18});
            for(ll j=0;j<=n2;j++){
                for(ll k=0;k<=n1;k++){
                    udp[j+k].first=min(udp[j+k].first,dp[j].first+ndp[k].first);
                    udp[j+k].second=min(udp[j+k].second,dp[j].first+ndp[k].second);
                    udp[j+k].second=min(udp[j+k].second,dp[j].second+ndp[k].first);
                    udp[j+k].second=min(udp[j+k].second,dp[j].second+ndp[k].second);
                }
            }
            dp=udp;
        }
    }
    ll n2=(ll)dp.size()-1;
    vector<pair<ll,ll>> udp(n2+1);
    for(ll i=0;i<=n2;i++){
        if(a[x]>0){
            udp[i].first=dp[i].first+a[x];
            udp[i].second=dp[i].second+a[x];
        }
        else{
            udp[i].first=1e18;
            udp[i].second=min(dp[i].first,dp[i].second)+a[x];
        }
    }
    return udp;
}
 
int main(){
    fast;
    ll t;
    t=1;
    while(t--){
        cin>>n;
        a.clear();
        a.resize(n);
        for(ll i=0;i<n;i++) cin>>a[i];
        string s;
        cin>>s;
        for(ll i=0;i<n;i++){
            if(s[i]=='1') a[i]=-a[i];
        }
        adj.clear();
        adj.resize(n);
        for(ll i=0;i<n-1;i++){
            ll u,v;
            cin>>u>>v;
            u--;
            v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        vector<pair<ll,ll>> dp=dfs(0,-1);
        for(ll i=0;i<n;i++){
            if(dp[i].first<1e18 || dp[i].second<0){
                cout<<i;
                break;
            }
        }
    }
}