Chỉ số hấp dẫn

Chỉ số hấp dẫn của xâu kí tự số \(S\) ứng với số nguyên tố \(p\) là số cặp vị trí khác nhau \(i, j\ (1 \le i \le j \le |S|)\)
thỏa mãn điều kiện: Số được tạo từ các kí tự thứ \(i\) đến kí tự thứ \(j\) của \(S\) chia hết cho \(p\). Chú ý rằng, số tạo được có thể chứa các chữ số \(0\) không có nghĩa ở đầu.

Ví dụ, với xâu \(S = '070070'\) và \(p = 13\) ta có các cặp vị trí: \((1, 1), (1, 5), (1, 6), (2, 5), (2, 6), (3, 3), (3, 4), (4, 4)\) và \((6, 6)\). Như vậy, chỉ số hấp dẫn của \(S\) ứng với \(p = 13\) là \(9\).

Yêu cầu: Cho xâu \(S\) và số nguyên tố \(p\), với mỗi truy vấn trong \(q\) truy vấn có dạng là cặp số \(L, R\), hãy cho biết chỉ số hấp dẫn của xâu được ghép lần lượt các kí tự thứ \(L\) đến kí tự thứ \(R\)
của \(S\).

Input

• Dòng đầu tiên chứa số nguyên tố \(p\ (2 \le p \le 10^9)\).
• Dòng thứ hai chứa xâu \(S\ (|S| \le 10^5)\) chỉ gồm các kí tự \('0'\) đến \('9'\).
• Dòng thứ ba chứa số nguyên \(q\) là số lượng truy vấn \((1 \le q \le 10^5)\).
• Mỗi dòng trong \(q\) dòng sau chứa hai số nguyên \(L\) và \(R\ (1 \le L \le R \le |S|)\).

Output

• Đưa ra thiết bị ra chuẩn \(q\) dòng, mỗi dòng một số nguyên là chỉ số hấp dẫn của xâu tương ứng truy vấn trong dữ liệu vào.

Example

13
070070
3
1 6
2 5
2 2

9
4
0

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(|S|, q \le 100\).
• Subtask \(2\) (\(40\%\) số điểm): \(p = 2\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc nào thêm.