Cho một xâu ~s~ độ dài ~n~ gồm các chữ cái tiếng Anh in thường được đánh số từ ~1~ đến ~n~, hãy đếm số lượng xâu palindrome là xâu con liên tiếp của xâu ~s~.

Kc97 nhận thấy bài toán này quá dễ so với trình độ thí sinh vì vậy anh quyết định nâng cấp bài toán như sau: thực hiện ~q~ truy vấn, truy vấn thứ ~i~ gồm hai số nguyên ~l_i, r_i~, in ra số lượng xâu palindrome liên tiếp của xâu con liên tiếp từ chữ cái ~l_i~ đến chữ cái ~r_i~ của xâu ~s~.

Input

Dòng đầu tiên chứa xâu ~s~ thỏa ~1 \le n \le 5000~.

Dòng thứ hai chứa một số nguyên dương ~q~ là số lượng truy vấn thỏa ~1 \le q \le 10^6~.

~q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~l_i, r_i~ thỏa ~1 \le l_i, r_i \le n~ mô tả truy vấn thứ ~i~.

Output

Gồm ~q~ dòng, dòng thứ ~i~ là đáp án của truy vấn thứ ~i~.

Samples

Sample Input 1

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

Sample Output 1

4
4
3
21
26

REF: Free Contest