Broken period

trade 100 string 0 book 0

So embarrassing

s t r i n g 0 s t r i n g 0 s t r i n g 0 s t r i n g 0 s t r i n g 0 s t r i

Only one last chance left

$R(s[i+l:i+2l-1])$ $R(s[i+l:i+2l-1])$ $R(s[i+l:i+2l-1])$ $R(s[i+l:i+2l-1])$ $R(s[i+l$ $R$ $R$ $R$ $R$ $r$ $r$ $r$ $r$

Cannot waste it anymore

2023.7

Given a string $s[1:n]$ of length $n$. There are $q$ queries, each given by two parameters $i$ and $r$. You need to find the number of $l$ such that the following conditions are satisfied:

• $1 \le l \le r$.
• $s[i:i+l-1]$ is lexicographically smaller than $s[i+l:i+2l-1]$.

Input

The first line contains an integer $c$, representing the subtask number. $c=0$ indicates that this test case is a sample.

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

The third 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 a query, guaranteed that $i + 2r - 1 \le n$.

Output

For each query, output a single integer on a new line representing the number of $l$ that satisfy the conditions.

Examples

Input 1

0
9 3
abacababa
1 4
2 4
3 3

Output 1

3
1
2

Constraints

For all data, $1 \le n, q \le 5 \times 10^5$, $1 \le i + 2r - 1 \le n$, and the string $s$ contains only lowercase letters.