Problem Description

Xiao Y is a college student who has recently been studying problems related to strings.

Xiao Y learned the following definitions about strings:

• Given a string $s[1: n]$ of length $n$, we define its substring $s[l: r]$ ($1 \leq l \leq r \leq n$) as the new string obtained by taking $s[l], s[l+1], \dots, s[r]$ and concatenating them in order.
• 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 order, i.e., reversing the string.
• Given two strings $a[1: n], b[1: n]$ of length $n$, we say $a$ is lexicographically smaller than $b$ if and only if there exists $1 \leq i \leq n$ such that for all $1 \leq j < i$, $a[j] = b[j]$, and $a[i] < b[i]$.

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

Given a string $s[1: n]$ of length $n$. There are $q$ queries, and each query gives two parameters $i, r$. You need to find how many $l$ satisfy the following conditions:

• $1 \leq l \leq r$.
• $s[i: i+l-1]$ is lexicographically smaller than $R(s[i+l: i+2l-1])$.

Xiao Y asks you for help to solve this problem.

Input Format

This problem contains multiple test cases.

The first line of input contains two integers $c, t$, representing the test point ID and the number of test cases. $c=0$ means this test point is the sample.

Then each test case is given as follows. For each test case:

The first line contains two positive integers $n, q$, representing the string length and the number of queries.

The second line contains a string $s$ of length $n$ consisting only of lowercase letters.

The next $q$ lines each contain two positive integers $i, r$, representing one query. It is guaranteed that $i+2r-1 \leq n$.

Output Format

For each query in each test case, output one line with an integer, representing the number of $l$ that satisfy the conditions.

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

4
0
3
2
0
2

见附件中的 string/string2.in。

见附件中的 string/string2.ans。

见附件中的 string/string3.in。

见附件中的 string/string3.ans。

见附件中的 string/string4.in。

见附件中的 string/string4.ans。

Hint

[Sample Explanation #1]

For the first query of the first test case:

• When $l = 1$, $s[i: i + l - 1] = \texttt{a}$, and $R(s[i + l: i + 2l - 1]) = \texttt{b}$.
• When $l = 2$, $s[i: i + l - 1] = \texttt{ab}$, and $R(s[i + l: i + 2l - 1]) = \texttt{ca}$.
• When $l = 3$, $s[i: i + l - 1] = \texttt{aba}$, and $R(s[i + l: i + 2l - 1]) = \texttt{bac}$.
• When $l = 4$, $s[i: i + l - 1] = \texttt{abac}$, and $R(s[i + l: i + 2l - 1]) = \texttt{baba}$.

In all 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]

The Constraints of this sample satisfy test point $5$.

[Sample Explanation #4]

The Constraints of this sample satisfy test points $24 \sim 25$.

[Constraints]

For all testdata, it is guaranteed that: $1 \le t \le 5$, $1 \le n \le 10 ^ 5$, $1 \le q \le 10 ^ 5$, $1 \le i + 2r - 1 \le n$, and the string $s$ consists only of lowercase letters.

Special property A: It is guaranteed that the string contains only characters $\texttt{a}$ and $\texttt{b}$, and each character independently chooses between $\texttt{a}$ and $\texttt{b}$ with equal probability.

Special property B: It is guaranteed that adjacent characters in the string are all different.

On Luogu, in this problem, Subtask 1 contains hack data, and it is guaranteed that $c=25$.

Translated by ChatGPT 5