Các subtask 1, 2, 3, 4 của bài này sẽ có đôi chút khác biệt về giới hạn của các biến. Các bạn lưu ý đọc kỹ đề. Với subtask 4, không có giới hạn gì thêm.

Giới hạn thời gian dành cho subtask 4 là ~3~ giây.

Bạn được cho một xâu ~s~ gồm các chữ cái tiếng Anh viết thường, và ~q~ truy vấn có dạng ~(l, r)~. Với mỗi truy vấn, bạn cần đếm xem có bao nhiêu xâu con liên tiếp của xâu ~s_{(l ... r)}~ là xâu đối xứng (palindrome).

(~s_{(l ... r)}~ là xâu con gồm các ký tự từ ~l~ đến ~r~ của ~s~, ~|s|~ là độ dài của xâu ~s~)

Dữ liệu vào

• Dòng đầu tiên gồm xâu ~s~ có độ dài không quá ~2 \times 10^5~.
• Dòng tiếp theo gồm một số nguyên dương ~q~ ~(q \le 2 \times 10^5)~ - số truy vấn cần xử lý.
• ~q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~l, r~ ~(1 \le l \le r \le |s|)~.

Dữ liệu ra

• Gồm ~q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.

Ví dụ

Ví dụ 1

Dữ liệu vào

abbab
5
1 3
1 4
1 5
2 5
3 5

Dữ liệu ra

4
6
8
6
4

Giải thích

• Các xâu đối xứng ở truy vấn thứ ~3~ là a (~2~ lần), b (~3~ lần), bb, abba, bab.