#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define mpr make_pair
#define fr first
#define sc second
inline int read(){
	int res=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {res=res*10+(c-'0');c=getchar();}
	return res*f;
}
const int N=2e5+5;
int n,m,fax[N][55],fin[N][55],lg[N];
int qs[N],hs[N],qs2[N],hs2[N],qs3[N],hs3[N],qs4[N],hs4[N],p[N],p2[N],p3[N],p4[N];
int query(int op,int l,int r){
	int k=lg[r-l+1];
	if (op==1) return max(fax[l][k],fax[r-(1<<k)+1][k]);
	return min(fin[l][k],fin[r-(1<<k)+1][k]);
}
void solve(){
	n=read(),m=read(),lg[0]=-1;
	for (int i=1;i<=n;i++) lg[i]=lg[i/2]+1;
	hs[n+1]=qs[0]=hs2[n+1]=qs2[0]=hs3[n+1]=qs3[0]=hs4[n+1]=qs4[0]=0,p[0]=p2[0]=p3[0]=p4[0]=1;
	for (int i=1;i<=n;i++){
		char ch;cin>>ch;
		fax[i][0]=fin[i][0]=ch-'a'+1;
	}
	for (int i=1;i<=n;i++){
		qs[i]=qs[i-1]*29+fax[i][0];
		p[i]=p[i-1]*29;
		qs2[i]=qs2[i-1]*41+fax[i][0];
		p2[i]=p2[i-1]*41;
		qs3[i]=qs3[i-1]*31+fax[i][0];
		p3[i]=p3[i-1]*31;
		qs4[i]=qs4[i-1]*67+fax[i][0];
		p4[i]=p4[i-1]*67;
	}
	for (int i=n;i>=1;i--){
		hs[i]=hs[i+1]*29+fax[i][0];
		hs2[i]=hs2[i+1]*41+fax[i][0];
		hs3[i]=hs3[i+1]*31+fax[i][0];
		hs4[i]=hs4[i+1]*67+fax[i][0];
	}
	for (int i=1;i<=lg[n];i++)
		for (int j=1;j+(1<<i)-1<=n;j++){
			fax[j][i]=max(fax[j][i-1],fax[j+(1<<(i-1))][i-1]);
			fin[j][i]=min(fin[j][i-1],fin[j+(1<<(i-1))][i-1]);
		}
	while (m--){
	    int l=read(),r=read(),siz=r-l+1,mx=query(1,l,r),mn=query(0,l,r),g=(1+siz)*siz/2-1;
		int gg=((qs[r]-qs[l-1]*p[r-l+1]==hs[l]-hs[r+1]*p[r-l+1])&&(qs2[r]-qs2[l-1]*p2[r-l+1]==hs2[l]-hs2[r+1]*p2[r-l+1])&&(qs3[r]-qs3[l-1]*p3[r-l+1]==hs3[l]-hs3[r+1]*p3[r-l+1])&&(qs4[r]-qs4[l-1]*p4[r-l+1]==hs4[l]-hs4[r+1]*p4[r-l+1]))*siz;
	    if (mx==mn) cout<<0<<'\n';
	    else cout<<g-gg<<'\n';
	}
}
signed main(){
	int T=read();
	while (T--) solve();
	return 0;
}

如何救治？