시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 512 MB124450.000%

문제

You are given a string $s$ and several queries. For the $i$-th query, calculate the number of different palindromic substrings of $s[l_i .. r_i]$. A substring is called palindromic if it reads the same from right to left as from left to right. Two substrings are considered different if they differ as strings.

입력

The first line contains a non-empty string $s$ consisting of lowercase English letters. The length of the string does not exceed $10^5$ characters.

The second line contains an integer $q$, the number of queries ($1 \leq q \leq 10^5$). Next $q$ lines contain queries. Each of these lines contains integers $l_i$ and $r_i$ separated by a space ($1 \leq l_i \leq r_i \leq |s|$).

출력

Output $q$ lines. The $i$-th line must contain one integer: the answer to the $i$-th query.

예제 입력 1

bbabaabbcabcabc
10
1 7
1 8
1 9
1 10
2 7
2 8
2 9
2 10
7 15
8 15

예제 출력 1

7
7
8
8
6
7
8
8
4
3