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.
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$
For each testcase, output the answer in $Q$ lines.