Cho một xâu \(s\) độ dài \(n\) chỉ gồm các ký tự Latin in thường (từ a đến z). Có \(q\) truy vấn, mỗi truy vấn cho hai số nguyên \(l\) và \(r\), hãy đếm có bao nhiêu cặp nghịch thế trong xâu con liên tiếp từ \(l\) đến \(r\).

Số cặp nghịch thế là số cặp \(i\), \(j\) sao cho \(i < j\) and ký tự ở vị trí \(i\) nằm sau ký tự ở vị trí \(j\) trong thứ tự từ điển. Ví dụ, xâu beac có \(3\) cặp nghịch thế, đó là \((1, 3)\), \((2, 3)\) và \((2, 4)\).

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 5 \cdot 10^5)\) là độ dài của xâu.
• Dòng tiếp theo chứa xâu \(s\) có độ dài \(n\) chỉ gồm các ký tự Latin in thường.
• Dòng tiếp theo chứa số nguyên \(q\) \((1 \leq q \leq 5 \cdot 10^5)\) là số truy vấn.
• Trong \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l\) và \(r\) \((1 \leq l \leq r \leq n)\) mô tả một truy vấn.

Output

• Gồm \(q\) dòng, mỗi dòng là số cặp nghịch thế của truy vấn tương ứng.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n, q \leq 5 \cdot 10^2\).
• Subtask \(2\) (\(25\%\) số điểm): \(n, q \leq 5 \cdot 10^3\).
• Subtask \(3\) (\(25\%\) số điểm): \(n, q \leq 5 \cdot 10^4\).
• Subtask \(4\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Example

7
adbcedc
4
1 4
3 5
4 7
2 4

2
0
3
2