思路对了，但是WA on 2.

#include<bits/stdc++.h>
using namespace std;
#define int long long
char d[1000009];
int p[1000009],cnt;//马拉车半径
int n;
int s1[1000009];//相同
int s2[1000009];//隔着相同
void _main(){
	int q;
	cin>>n>>q;
	for(int i=0;i<=n+10;i++){
		d[i]=p[i]=s1[i]=s2[i]=0;
	}
	cnt=0;
	string s;
    cin>>s;
    s='~'+s;
    s1[1]=s2[1]=1;
    s2[2]=2,s1[2]=2-(s[2]==s[1]);
    for(int i=3;i<=n;i++){
    	if(s[i]==s[i-1]){
    		s1[i]=s1[i-1];
		}else{
			s1[i]=i;
		}
		if(s[i]==s[i-2]){
			s2[i]=s2[i-2];
		}else{
			s2[i]=i;
		}
	}
    d[0]='~';
    cnt=0;
    for(int i=1;i<=n;i++){
    	d[++cnt]='|';
    	d[++cnt]=s[i];
	}
      for(int t=1,r=0,mid=0;t<=cnt;++t){
	    if(t<=r) p[t]=min(p[(mid<<1)-t],r-t+1);
	    while(d[t-p[t]]==d[t+p[t]]) ++p[t];
	    if(p[t]+t>r) r=p[t]+t-1,mid=t;
      }
	  for(int i=1;i<=q;i++){
	  	int l,r;
	  	cin>>l>>r;
	  	if(s1[r]<=l){//全都一样答案为0
	  		cout<<0<<endl;
	  		continue;
		  }
	  	int mid;
	  	mid=r+l;
	  	int ans;
	  	ans=0;
	  	if(p[mid]<2*r-mid+1){//全局是否回文
	  		ans+=r-l+1;
		}
		int nn;
		nn=r-l+1;
		nn--;//后续不计算全局
		int js,os;//长度为奇数的贡献个偶数贡献
		os=(nn/2*2+2)*(nn/2)/2;
		js=(1+nn)*(nn)/2-os;
		js--;//不算长度为1
		ans+=os;//偶数一定可以构造
		if(s2[r]>l+1||s2[r-1]>l+1){//是否为形如abababa的字符串，如果是，则奇数没有贡献
			ans+=js;
		}
		cout<<ans<<endl;
	  }
}


signed main(){
	int t;
	cin>>t;	
	while(t--){
		_main();
	}
	return 0;
}