Bob likes strings.

Bob considers a string that repeats twice to be beautiful. For example, aa, sese, abcabc, baabaa, and abababab are beautiful strings, while ab, aadead, sesese, and abba are not. More specifically, a string $S$ is beautiful if it can be written as the concatenation of two identical strings, i.e., there exists a string $P$ such that $S = PP$.

Bob has a string $T = T_1T_2 \dots T_n$ of length $n$. He wants to know, for a given substring $Q = T[l \dots r]$ of $T$, how many distinct beautiful strings are contained as substrings within $Q$. If two strings are identical, they are not considered distinct, regardless of their positions.

Bob has $q$ different queries, and you need to calculate the answer for each query efficiently.

Input

The first line contains two integers $n$ and $q$. The second line contains a string $T$ consisting only of lowercase letters 'a' and 'b'.

The next $q$ lines each contain two integers $l$ and $r$, representing a query.

Output

Output $q$ lines, each containing an integer representing the answer.

Examples

Input 1

11 5
aabaabaaaab
1 11
1 6
7 10
5 5
3 8

Output 1

5
2
2
0
2

Note

In the string $T$, the distinct beautiful strings are aa, aaaa, abaaba, aabaab, and baabaa.

Constraints

• For the first 10% of the data, $n \le 100$.
• For the first 20% of the data, $n \le 500$.
• For the first 40% of the data, $n \le 5000$.
• For another 20% of the data, it is guaranteed that the total number of beautiful substrings in $T$ does not exceed $10^6$, where strings at different positions are considered different.
• For another 20% of the data, $q = 1$.
• For 100% of the data, $1 \le n, q \le 200000$, $1 \le l \le r \le n$, and $T$ consists only of lowercase letters 'a' and 'b'.