Đếm xâu đối xứng trong đoạn

Một xâu được gọi là đối xứng (palindrome) nếu đọc từ trái sang phải và từ phải sang trái đều cho cùng một dãy ký tự, chẳng hạn abba, aba, c.

Cho xâu \(S\) gồm \(N\) ký tự, đánh số từ \(1\) đến \(N\). Xâu con \(S[i..j]\) (\(1 \le i \le j \le N\)) là dãy ký tự \(S_i S_{i+1} \ldots S_j\); hai xâu con ở hai vị trí khác nhau được tính là khác nhau dù nội dung có thể giống nhau.

Có \(T\) truy vấn, mỗi truy vấn cho hai số \(a, b\) (\(a \le b\)). Với mỗi truy vấn, hãy đếm số xâu con đối xứng \(S[i..j]\) thỏa mãn \(a \le i \le j \le b\).

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(T\).
• Dòng thứ hai chứa xâu \(S\) độ dài \(N\), gồm các chữ cái tiếng Anh (phân biệt chữ hoa và chữ thường).
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\).

Output

• In ra \(T\) dòng, dòng thứ \(k\) là đáp án của truy vấn thứ \(k\).

Constraints

• \(1 \le N, T \le 1000\)
• \(1 \le a \le b \le N\)

Sample Input 1

5 3
abaab
1 3
2 5
4 4

Sample Output 1

4
6
1

Explanation

Với truy vấn \((1,3)\) xét xâu aba: các xâu con đối xứng là a, b, a, aba nên có \(4\) xâu.