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≤T≤10$, $1≤length≤1000, 1≤Q≤100000, 1≤l≤r≤length$
For each testcase, output the answer in $Q$ lines.
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.
$ 不同回文子串的数量 = P - 2 $