#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,q,dp[4005][4005];
char s[4005];
int main(){int _o,T;
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    for(cin>>_o>>T;T--;){
        cin>>n>>q>>(s+1);
        for(int j=1;(j<<1)<=n;j++)
            for(int i=1;i+(j<<1)-1<=n;i++){
                int ii=i+(j<<1)-1;
                if(s[i]<s[ii])dp[i][j]=true;
                else if(s[i]>s[ii])dp[i][j]=false;
                else dp[i][j]=dp[i+1][j-1];
            }

        for(int i=1,a,b;i<=q;i++){
            cin>>a>>b;
            int ans=0;
            for(int j=1;j<=b;j++)
                ans+=dp[a][j];
            cout<<ans<<endl;
        }
    }
    return 0;
}