Binary Removals

#include <bits/stdc++.h>
#define int long long 
using namespace std;
signed main() {
	// your code goes here
      int t;cin>>t;
      while(t--){
          int n,x,k;
          cin>>n>>x>>k;
          int a=0,b=0,p=0;
          string s; cin>>s;
          for(auto x:s){
            if(x=='1')a++;
            if(x=='0'){
                p+=a;
            }
          }
          int res=2;
          if(p<=x && p%k==0)res=1;
          cout<<res<<"\n";
      }    
}