CA loves strings, especially loves the palindrome strings.
One day he gets a string, he wants to know how many palindromic substrings in the substring $S[l,r]$.
Attantion, each same palindromic substring can only be counted once.
Input
First line contains $T$ denoting the number of testcases.
$T$ testcases follow. For each testcase:
First line contains a string $S$. We ensure that it is contains only with lower case letters.
Second line contains a interger $Q$, denoting the number of queries.
Then $Q$ lines follow, In each line there are two intergers $l,r$, denoting the substring which is queried.
$1 \le T \le 10,~1 \le length \le 1000,~1 \le Q \le 100000,~1 \le l \le r \le length$
Output
For each testcase, output the answer in $Q$ lines.
Sample Input
1
abba
2
1 2
1 3
Sample Output
2
3
Hint
In first query, the palindromic substrings in the substring $S[1,2]$ are "a","b".
In second query, the palindromic substrings in the substring $S[1,2]$ are "a","b","bb".
Note that the substring "b" appears twice, but only be counted once.
You may need an input-output optimization.
