Xiao Y é um estudante universitário e recentemente tem pesquisado problemas sobre strings.

Xiao Y aprendeu as seguintes definições sobre strings:

• Dada uma string $s[1:n]$ de comprimento $n$, definimos a sua substring $s[l:r]$ ($1\leq l\leq r\leq n$) como a nova string obtida selecionando $s[l],s[l+1],\ldots,s[r]$ e concatenando-os nessa ordem.
• Dada uma string $s[1:n]$ de comprimento $n$, definimos o resultado da sua inversão, $R(s)$, como a concatenação de $s[n],s[n-1],\ldots,s[1]$, nessa ordem, ou seja, a string formada concatenando os caracteres em ordem inversa.
• Dadas duas strings $a[1:n],b[1:n]$, ambas de comprimento $n$, definimos que $a$ é lexicograficamente menor que $b$ se, e somente se, existe $1\leq i\leq n$ tal que, para todo $1\leq j<i$, $a[j]=b[j]$, e $a[i]<b[i]$.

Depois de aprender essas definições, Xiao Y pensou no seguinte problema:

É dada uma string $s[1:n]$ de comprimento $n$. Há $q$ consultas, cada uma fornecendo dois parâmetros $i,r$. Você precisa determinar quantos valores de $l$ satisfazem as seguintes condições:

• $1\leq l\leq r$.
• $s[i:i+l-1]$ é lexicograficamente menor que $R(s[i+l:i+2l-1])$.

Xiao Y pede a sua ajuda para resolver esse problema.

Entrada

Leia os dados do arquivo string.in.

Este problema contém vários casos de teste.

A primeira linha da entrada contém dois inteiros $c,t$, que representam, respectivamente, o número do ponto de teste e o número de casos de teste. $c=0$ indica que o ponto de teste é um exemplo.

Em seguida, são fornecidos os casos de teste, um após o outro. Para cada caso de teste:

A primeira linha contém dois inteiros positivos $n,q$, que representam o comprimento da string e o número de consultas.

A segunda linha contém uma string $s$ de comprimento $n$, formada apenas por letras minúsculas.

Cada uma das próximas $q$ linhas contém dois inteiros positivos $i,r$, que representam uma consulta. É garantido que $i+2r-1\leq n$.

Saída

Escreva no arquivo string.out.

Para cada consulta de cada caso de teste, imprima uma linha com um inteiro: o número de valores de $l$ que satisfazem as condições.

Exemplos

Entrada 1

0 2
9 3
abacababa
1 4
2 4
3 3
9 3
abaabaaba
1 4
2 4
3 3

Saída 1

4
0
3
2
0
2

Explicação

Para a primeira consulta do primeiro caso de teste:

• Quando $l=1$, $s[i:i+l-1]=a$ e $R(s[i+l:i+l+l-1])=b$.
• Quando $l=2$, $s[i:i+l-1]=ab$ e $R(s[i+l:i+l+l-1])=ca$.
• Quando $l=3$, $s[i:i+l-1]=aba$ e $R(s[i+l:i+l+l-1])=bac$.
• Quando $l=4$, $s[i:i+l-1]=abac$ e $R(s[i+l:i+l+l-1])=baba$.

Em todos esses quatro casos, $s[i:i+l-1]$ é lexicograficamente menor que $R(s[i+l:i+2l-1])$, portanto a resposta é $4$.

Exemplo 2

Consulte string/string2.in e string/string2.ans no diretório do participante.

Este exemplo satisfaz os limites do ponto de teste 5.

Exemplo 3

Consulte string/string3.in e string/string3.ans no diretório do participante.

Exemplo 4

Consulte string/string4.in e string/string4.ans no diretório do participante.

Este exemplo satisfaz os limites dos pontos de teste $24\sim 25$.

Restrições

Para todos os dados de teste, é garantido que $1\leq t\leq 5$, $1\leq n\leq 10^5$, $1\leq q\leq 10^5$, $1\leq i+2r-1\leq n$, e que a string $s$ contém apenas letras minúsculas.

• Propriedade especial A: é garantido que a string contém apenas os caracteres a e b, sendo cada caractere escolhido entre a e b de forma independente e com igual probabilidade.
• Propriedade especial B: é garantido que caracteres adjacentes da string são diferentes.