Hôm nay, Orange bước vào kì thi International Olympiad in Informatics, và gặp một bài toán rất khó như sau:

Cho một xâu ~s~. Có ~q~ câu hỏi cần được giải quyết. Mỗi câu hỏi đưa ra 2 số nguyên dương ~l, r~, yêu cầu đếm số lượng xâu con liên tiếp nằm trong đoạn ~[l, r]~ và phải là một xâu đối xứng.

Yêu cầu

Hãy giúp Orange giải bài toán trên.

Input

• Dòng đầu tiên chứa xâu ~s~ (~|s| \leq 5000~);
• Dòng thứ 2 chứa một số nguyên dương ~q~ (~q \leq 10^{6}~);
• ~q~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương ~l, r~ là từng câu hỏi.

Output

• Gồm ~q~ dòng, dòng thứ ~i~ là đáp án cho câu hỏi thứ ~i~.

Sample Input

aaaba
2
1 3
1 5

Sample Output

6
9

Explanation

• Câu hỏi 1: Xâu con từ 1 đến 3 là ~aaa~. Vậy có 6 xâu con liên tiếp đối xứng là: ~a, a, a, aa, aa, aaa~.
• Câu hỏi 2: Xâu con từ 1 đến 5 là ~aaaba~. Vậy có 9 xâu con liên tiếp đối xứng là: ~a, a, a, b, a, aa, aa, aaa, aba~.

Giới Hạn

• 25% số test ứng với 25% số điểm có ~|s| \leq 50, q \leq 100~;
• 25% số test ứng với 25% số điểm có ~|s| \leq 100, q \leq 100~;
• 25% số test ứng với 25% số điểm có ~|s| \leq 100, q \leq 10^{6}~;
• 25% test còn lại ứng với 25% số điểm có ~|s| \leq 5000, q \leq 10^{6}~;