You are given a string ~S~ with length ~L~. Furthermore, you are given ~Q~ queries. Each query will be of the following format:

• ~l_i~ ~r_i~, asking for the number of substrings in string ~S~ between position ~l_i~ and ~r_i~ that are palindromic.

A string ~P~ is a palindrome if it meets the following condition: ~P = P_l P_{l+1} \cdots P_r = P_r P_{r-1} P_{r-2} \cdots P_l~.

Input Specification

The first line contains a string ~S~, with a length ~L~ ~(1 \le L \le 2000)~. The string will only consist of lowercase letters.

The second line of input contains an integer ~Q~ ~(1 \le Q \le 10^6)~.

The next ~Q~ lines of input will contain 2 space separated integers, ~l_i~ and ~r_i~ ~(1 \le l_i \le r_i \le N)~.

Output Specification

You are to output ~Q~ integers, the solutions to the queries.

Subtasks

Subtask 1 [30%]

~1 \le L \le 100~

~1 \le Q \le 10~

Subtask 2 [70%]

No further constraints.

Sample Input

aaaaabbbaa
5
7 9
4 6
6 7
1 8
1 10

Sample Output

4
4
3
21
26