Problem Description

A string is palindromic if it reads the same from left to right.
Given a string $S[1..n]$, Little Q will ask you $m$ queries. For each query, Little Q will give you $2$ integers $l_i,r_i$, you need to find the number of ways to cut the continous substring $S[l_i..r_i]$ into two non-empty palindromic strings. That is, find the number of $k(l_i\leq k<r_i)$ satisfying $S[l_i..k]$ and $S[k+1..r_i]$ are both palindromic strings.

Input

The first line of the input contains an integer $T(1\leq T\leq10)$, denoting the number of test cases.
In each test case, there are $2$ integers $n,m(2\leq n\leq 100000,1\leq m\leq 100000)$ in the first line, denoting the length of $S$ and the number of queries.
In the next line, there is a string $S$ consists of $n$ lower-case English letters.
Then in the following $m$ lines, there are $2$ integers $l_i,r_i(1\leq l_i<r_i\leq n)$ in each line, denoting a query.

Output

For each query, print a single line containing an integer, denoting the answer.

1
10 5
aaaabababb
1 4
1 5
4 9
6 10
1 10

3
1
3
1
0