#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define MAXN 100000
int L[MAXN+10]; //L[i] stores largest index < i such that substring S[L[i],i] contains more than K 1s/0s
LL pre[MAXN+10];//prefix sum of array i-L[i] to calculate subarray sums.
char s[MAXN+10];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        memset(L,0,sizeof(L));
        int n,q,l,r,k;
        scanf("%d %d %d %s",&n,&k,&q,s+1);
        int cnt[2]={};              //cnt[i] stores current count of j
        map <int, int> mymap[2];    //mymap[i][j] stores the largest index till where i j's were present
        for(int i=1; i<=n; i++){
            cnt[s[i]-'0']++;
            for(int j=0; j<2; j++)
                L[i]=max(L[i],mymap[j][cnt[j]-k]);
            mymap[s[i]-'0'][cnt[s[i]-'0']]=i;
            pre[i]=pre[i-1]+(LL)(i-L[i]);
        }
        while(q--){
            scanf("%d %d",&l,&r);
            int p=min((LL)(lower_bound(L+1,L+n+1,l)-L),(LL)r+1ll);  //count how many L[i] are less than l
            LL ans=pre[r]-pre[p-1];                                 //all substrings of S[l,p-1] are valid
            if(p>l) ans += ((LL)(p-l)*(LL)(p-l+1))/2;               //add to answer: i-L[i] from i=p to r.
            printf("%lld\n",ans);
        }
    }
    return 0;
}
mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(double x, char c){printf("%.15f",x);mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
template<class T, class S> void writerLn(T x, S y){writer(x,' ');writer(y,'\n');}
template<class T, class S, class U> void writerLn(T x, S y, U z){writer(x,' ');writer(y,' ');writer(z,'\n');}
template<class T> void writerArr(T x[], int n){int i;if(!n){mypc('\n');return;}rep(i,n-1)writer(x[i],' ');writer(x[n-1],'\n');}
 
char memarr[17000000]; void *mem = memarr;
#define MD 1000000007
 
ll solve_slow(int N, char S[], int K){
  int i, j, cnt[2] = {};
  ll res = 0;
 
  j = 0;
  rep(i,N){
    while(j < N && cnt[S[j]]+1 <= K) cnt[S[j++]]++;
    cnt[S[i]]--;
    res += j-i;
  }
  return res;
}
 
int T;
int N, K, Q, L, R;
char S[110000];
 
ll toL[110000], toR[110000], sum[110000];
int cnt[2];
 
int main(){
  int i, j, k;
  ll res, tmp;
 
  reader(&T);
  while(T--){
    reader(&N, &K, &Q, S);
    rep(i,N) S[i] -= '0';
 
    cnt[0] = cnt[1] = 0;
    j = 0;
    rep(i,N){
      while(j < N && cnt[S[j]]+1 <= K) cnt[S[j++]]++;
      toL[i] = j-1;
      cnt[S[i]]--;
    }
    
    cnt[0] = cnt[1] = 0;
    j = N-1;
    for(i=N-1;i>=0;i--){
      while(j >= 0 && cnt[S[j]]+1 <= K) cnt[S[j--]]++;
      toR[i] = j+1;
      cnt[S[i]]--;
    }
 
    sum[0] = 0;
    rep(i,N) sum[i+1] = sum[i] + toL[i];
 
    while(Q--){
      reader(&L,&R);
      L--; R--;
 
      k = toR[R] - 1;
      if(L <= k){
        res = sum[k+1] - sum[L] + (R - k) * R;
        res -= (ll)(L+R-2) * (R-L+1) / 2;
      } else {
        res = (ll)(R-L+2) * (R-L+1) / 2;
      }
 
      writerLn(res);
 
//      tmp = solve_slow(R-L+1, S+L, K);
//      writerLn(res, tmp);
//      assert(res==tmp);
    }
  }
 
  return 0;
}