Young Y is a university student who has recently been researching problems related to strings. Young Y has learned the following definitions regarding strings: Given a string $s[1 : n]$ of length $n$, we define its substring $s[l : r]$ ($1 \le l \le r \le n$) as the new string obtained by selecting $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, which is the string reversed. * Given two strings $a[1 : n]$ and $b[1 : n]$ both of length $n$, we define $a$ to be lexicographically smaller than $b$ if and only if there exists $1 \le i \le n$ such that for all $1 \le j < i$, $a[j] = b[j]$, and $a[i] < b[i]$.

After learning the above definitions, Young Y thought of 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 \le l \le r$. $s[i : i + l - 1]$ is lexicographically smaller than $R(s[i + l : i + 2l - 1])$.

Young Y would like your help to solve this problem.

Input

Read the data from the file string.in. There are multiple test cases. The first line of the input contains two integers $c$ and $t$, representing the test case ID and the number of test cases, respectively. $c = 0$ indicates that this test case is a sample. Then, each test case is provided sequentially. For each test case: The first line contains two positive integers $n$ and $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$ and $r$, representing a query. It is guaranteed that $i + 2r - 1 \le n$.

Output

Output to the file string.out. For each query in each test case, output one integer per line, representing the number of $l$ that satisfy the conditions.

Examples

Input 1

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

Output 1

4
0
3
2
0
2

Note

For the first query of the first test case: When $l = 1$, $s[i : i + l - 1] = \text{a}$, $R(s[i + l : i + l + l - 1]) = \text{b}$. When $l = 2$, $s[i : i + l - 1] = \text{ab}$, $R(s[i + l : i + l + l - 1]) = \text{ca}$. When $l = 3$, $s[i : i + l - 1] = \text{aba}$, $R(s[i + l : i + l + l - 1]) = \text{bac}$. When $l = 4$, $s[i : i + l - 1] = \text{abac}$, $R(s[i + l : i + l + l - 1]) = \text{baba}$. In these four cases, $s[i : i + l - 1]$ is lexicographically smaller than $R(s[i + l : i + 2l - 1])$, so the answer is 4.

Examples 2

See string/string2.in and string/string2.ans in the contestant directory. The data range for this sample satisfies test case 5.

Examples 3

See string/string3.in and string/string3.ans in the contestant directory.

Examples 4

See string/string4.in and string/string4.ans in the contestant directory. The data range for this sample satisfies test cases 24 ~ 25.

Constraints

For all test cases, 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$ contains only lowercase letters.

• Special Property A: The string is guaranteed to contain only characters 'a' and 'b', and each character is chosen independently and with equal probability from 'a' and 'b'.
• Special Property B: The string is guaranteed to have no two adjacent characters that are the same.