팰린드롬 세기

모의고사를 열고 싶었지만 낼 문제가 없던 운영진은 머릿속에 떠오른 두 낱말, 팰린드롬과 자료구조를 섞어 문제를 내기로 했다.

승현이가 알파벳 소문자로만 이루어진 문자열 $S$를 만들었다. $1 \le i \le j \le |S|$인 두 정수 $i$, $j$에 대해 $S[i..j]$는 $S$의 $i$번째 문자부터 $j$번째 문자까지를 차례로 이어 붙인 부분문자열이다.

질의 하나는 두 정수 $a$, $b$로 주어진다. 각 질의마다 $S[a..b]$ 안에 놓인 팰린드롬이 몇 개인지 세면 된다. 다시 말해 $a \le x \le y \le b$이면서 $S[x..y]$가 팰린드롬인 순서쌍 $(x, y)$의 개수를 구한다. 같은 문자열이라도 시작 위치가 다르면 따로 센다.

첫째 줄에 승현이가 만든 문자열 $S$가 주어진다. $S$는 알파벳 소문자 a부터 z까지로만 이루어져 있고, 길이는 $1 \le |S| \le 100\,000$이다.

둘째 줄에 질의의 개수 $Q$ ($1 \le Q \le 300\,000$)가 주어진다. 이어지는 $Q$개의 줄에 각각 두 정수 $a_i$와 $b_i$ ($1 \le a_i \le b_i \le |S|$)가 주어진다.

질의마다 $S[a_i..b_i]$ 안에 놓인 팰린드롬의 개수를 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.

문자열 $T = t_1 t_2 t_3 \cdots t_n$이 팰린드롬이라는 것은 앞에서 뒤로 읽으나 뒤에서 앞으로 읽으나 같다는 뜻이다. 즉 $t_1 t_2 t_3 \cdots t_{n-1} t_n = t_n t_{n-1} \cdots t_3 t_2 t_1$을 만족하는 $T$가 팰린드롬이다. 길이가 1인 문자열은 언제나 팰린드롬이다.

$|S|$는 문자열 $S$의 길이이다.