Cho xâu ~s~ gồm ~N~ chữ cái latin thường, các ký tự được đánh số từ ~1~ đến ~N~.

Có ~Q~ truy vấn, mỗi truy vấn gồm hai số ~L, R~. Với mỗi truy vấn, hãy đếm số xâu con đối xứng (palindrome) của ~s~ nằm hoàn toàn trong đoạn ~[L, R]~. Hai xâu con được coi là khác nhau nếu vị trí bắt đầu hoặc vị trí kết thúc khác nhau.

Input

• Dòng đầu tiên chứa xâu ~s~.
• Dòng thứ hai chứa số nguyên ~Q~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~L, R~ (~1 \le L \le R \le N~).

Output

In ra ~Q~ dòng, dòng thứ ~i~ là đáp án của truy vấn thứ ~i~.

Giới hạn

• ~s~ chỉ gồm các chữ cái latin thường.
• ~1 \le L \le R \le N~

Vào/ra bằng file

• Dữ liệu vào: đọc từ file CNTPAL.INP.
• Kết quả: ghi ra file CNTPAL.OUT.