Trong một hệ thống truyền thông tin bảo mật giữa các thiết bị IoT, dữ liệu đôi khi được chèn thêm các xâu đối xứng để đánh dấu các đoạn dữ liệu đặc biệt, ví dụ như mã xác thực, mã kiểm tra hoặc mã khóa tạm thời,.... Xâu đối xứng là xâu mà khi đọc từ trái sang phải cũng thu được kết quả giống như đọc từ phải sang trái.

Để phân tích nhật kí truyền thông tin được ghi lại dưới dạng xâu các kí tự thường. Do yêu cầu đặc biệt, người quản trị hệ thống cần biết trong mỗi đoạn kí tự được chỉ định có bao nhiêu xâu con liên tiếp là xâu đối xứng.

Yêu cầu: Cho ~s~ là một xâu kí tự có độ dài ~n~ đại diện cho nhật kí truyền thông tin được ghi lại và ~q~ truy vấn. Với mỗi truy vấn cho ~2~ chỉ số ~u, v~ (với ~1 \le u \le v \le n~) tương ứng với một đoạn kí tự được chỉ định gồm các kí tự từ vị trí ~u~ đến vị trí ~v~ của xâu ~s~, hãy xác định số lượng xâu con liên tiếp ~s_i, s_{i+1},\dots,s_j~ (~u \le i \le j \le v~) là xâu đối xứng.

Input

• Dòng đầu tiên chứa xâu kí tự ~s~ gồm ~n~ chữ cái in thường thuộc bảng chữ cái tiếng Anh (với ~n \le 5 \cdot 10^4~).

• Dòng thứ hai chứa số nguyên dương ~q~ (~q \le 5 \cdot 10^4~) là số lượng truy vấn.

• ~q~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên ~u, v~ (~1 \le u \le v \le n~) mô tả một truy vấn. Các số trên một dòng cách nhau bởi một dấu cách.

Output

• Gồm ~q~ dòng, dòng thứ ~i~ ghi số lượng xâu con liên tiếp là xâu đối xứng tương ứng với truy vấn thứ ~i~ cho trong dữ liệu.

Scoring

Sample Input 1

abacaab
4
1 3
3 6
2 7
5 6

Sample Output 1

4
6
8
3

Notes

Với truy vấn ~u = 1, v = 3~ có ~4~ xâu con đối xứng ~\{a\}, \{b\}, \{a\}, \{aba\}~.