Problem Description

Xiao Y is a university student currently researching string-related problems.

Xiao Y understands the following definitions about strings:

• Given a string \( s[1:n] \) of length \( n \), we define its substring \( s[l:r] \) (where \( 1 \leq l \leq r \leq n \)) as the new string obtained by concatenating \( s[l], s[l+1], \dots, s[r] \) in sequence.
• Given a string \( s[1:n] \) of length \( n \), we define its reversed result \( R(s) \) as the string obtained by concatenating \( s[n], s[n-1], \dots, s[1] \) in sequence, i.e., the string obtained by reversing the order of characters.
• Given two strings \( a[1:n] \) and \( b[1:n] \) of the same length \( n \), we define \( a \) as lexicographically smaller than \( b \) if and only if there exists an \( i \) (where \( 1 \leq i \leq n \)) such that for any \( j \) (where \( 1 \leq j < i \)), \( a[j] = b[j] \) and \( a[i] < b[i] \).

After understanding these definitions, Xiao Y came up with the following problem:

Given a string \( s[1:n] \) of length \( n \). There are \( q \) queries, each providing two parameters \( i \) and \( r \). You need to find how many \( l \) satisfy the following conditions:
- \( 1 \leq l \leq r \).
- The substring \( s[i:i+l-1] \) is lexicographically smaller than \( R(s[i+l:i+2l-1]) \).

Xiao Y seeks your help to solve this problem.

Input Format

This problem contains multiple test cases.

The first line of input contains two integers \( c \) and \( t \), representing the test point number and the number of test cases, respectively. \( c=0 \) indicates that this test point is a sample.

For each test case:

The first line contains two positive integers \( n \) and \( q \), representing the length of the string and the number of queries, respectively.

The second line contains a string \( s \) of length \( n \) consisting only of lowercase letters.

The next \( q \) lines, each containing two positive integers \( i \) and \( r \), represent a query. It is guaranteed that \( i+2r-1 \leq n \).

Output Format

For each query in every test case, output a single integer on a new line, representing the number of \( l \) that satisfy the conditions.

Sample Input and Output

Input Sample #1

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

Output Sample #1

4
0
3
2
0
2

Input Sample #2

See the attached file string/string2.in.

Output Sample #2

See the attached file string/string2.ans.

Input Sample #3

See the attached file string/string3.in.

Output Sample #3

See the attached file string/string3.ans.

Input Sample #4

See the attached file string/string4.in.

Output Sample #4

See the attached file string/string4.ans.

Notes/Hints

[Sample Explanation #1]

For the first query of the first dataset:
- When \( l = 1 \), \( s[i:i+l-1] = \texttt{a} \), \( R(s[i+l:i+2l-1]) = \texttt{b} \).
- When \( l = 2 \), \( s[i:i+l-1] = \texttt{ab} \), \( R(s[i+l:i+2l-1]) = \texttt{ca} \).
- When \( l = 3 \), \( s[i:i+l-1] = \texttt{aba} \), \( R(s[i+l:i+2l-1]) = \texttt{bac} \).
- When \( l = 4 \), \( s[i:i+l-1] = \texttt{abac} \), \( R(s[i+l:i+2l-1]) = \texttt{baba} \).

In these four cases, \( s[i:i+l-1] \) is lexicographically smaller than \( R(s[i+l:i+2l-1]) \). Therefore, the answer is \( 4 \).

[Sample Explanation #2]

This sample satisfies the constraints of test point 5.

[Sample Explanation #4]

This sample satisfies the constraints of test points 24 to 25.

[Data Range]

For all test data, it is guaranteed that: \( 1 \leq t \leq 5 \), \( 1 \leq n \leq 10^5 \), \( 1 \leq q \leq 10^5 \), \( 1 \leq i + 2r - 1 \leq n \), and the string \( s \) consists only of lowercase letters.

Special Condition A: The string contains only characters \( \texttt{a} \) and \( \texttt{b} \), and each character is independently and equally likely to be chosen from \( \texttt{a} \) and \( \texttt{b} \).

Special Condition B: Adjacent characters in the string are guaranteed to be different.

见题面 Input 部分

见题面 Output 部分