Nrd (Người ra đề) có bài toán sau: Cho một xâu s chỉ gồm |s| chữ cái tiếng Anh in thường được đánh số từ 1 đến |s|, 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 Free Contest, vì vậy sau khi nhận được bài này từ Nrd, anh quyết định nâng cấp bài toán như sau: Cho một xâu s chỉ gồm |s| chữ cáitiếng Anh in thường và q truy vấn, truy vấn thứ i gồm hai số nguyên li, ri (1 ≤ li ≤ ri ≤ |s|). Với mỗi truy vấn i, hãy in ra số lượng xâu palindrome liên tiếp là xâu con liên tiếp của xâu con liên tiếp từ chữ cái li đến chữ cái ri của xâu s

Input

• Dòng đầu tiên chứa xâu s (1 ≤ |s| ≤ 5000).

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

• q dòng tiếp theo, dòng thứ i chứa hai số nguyên li, ri (1 ≤ li, ri ≤ |s|) 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

Sample

Input #1

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

Output #1

4
4
3
21
26

Problem source: Free Contest 38