Sau khi khám phá gần như toàn bộ Việt Nam, ledinhbaonam, PhuocThien, uia và Prototype tiếp tục hành trình đến Nghệ An — quê hương của Chủ tịch Hồ Chí Minh, vị lãnh tụ vĩ đại của dân tộc Việt Nam.

Tại khu lưu trữ đặc biệt, cả nhóm phát hiện một bản mã cổ gồm một xâu ký tự \(S\) chỉ chứa các chữ cái Latin thường.

Theo ghi chép để lại, một đoạn thông điệp được gọi là đoạn lãnh tụ nếu thỏa mãn:

• Đoạn đó là palindrome.

Tuy nhiên, hệ thống cổ còn đưa ra thêm \(q\) nghi thức đặc biệt.

Mỗi nghi thức gồm hai số nguyên \(l, r\), yêu cầu:

Xét riêng đoạn con:

hãy đếm số lượng xâu con liên tiếp của đoạn này là đoạn lãnh tụ.

Nhiệm vụ

• Với mỗi truy vấn, hãy in ra số lượng đoạn lãnh tụ trong đoạn được yêu cầu.

Input

• Dòng đầu chứa ba số nguyên \(n, q, k\). (\(1 \le n, q \le 3000\), \(1 \le k \le 26\))
• Dòng thứ hai chứa xâu \(S\). (\(|S| = n\))
• \(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

• Với mỗi truy vấn, in ra một số nguyên là đáp án tương ứng.

Example

6 1 2
aabbaa
1 6

11

1 6

a(1→1)
a(2→2)
b(3→3)
b(4→4)
a(5→5)
a(6→6)
aa(1→2)
bb(3→4)
aa(5→6)
abba(2→5)
aabbaa(1→6)

20 3 3
abacabadabacabaabba
1 20
3 15
8 20

37
23
22