Trong buổi tuyên truyền về an toàn trên không gian mạng, nhà trường giới thiệu một hệ thống nhận diện các số điện thoại có dấu hiệu quảng cáo hoặc lừa đảo. Để bảo vệ quyền riêng tư cá nhân, hệ thống này chỉ lưu trữ \(4\) chữ số cuối của mỗi số điện thoại, gọi là mã đuôi.

Một mã đuôi (gồm đúng \(4\) chữ số) được gọi là mã nghi vấn nếu nó thỏa mãn đồng thời \(3\) điều kiện sau:

1. Chữ số đầu tiên là \(2\) hoặc \(0\);
2. Chữ số cuối cùng là \(2\) hoặc \(6\);
3. Hai chữ số ở giữa giống nhau.

Ví dụ: 2556, 0006, 2112 là các mã nghi vấn; còn 2229, 9129 không là mã nghi vấn.

Hệ thống thu thập \(n\) số điện thoại, các số điện thoại được đánh số từ \(1\) đến \(n\). Số điện thoại thứ \(i\) (\(1 \le i \le n\)) có mã đuôi là \(s_i\). Hệ thống ghi nhận \(q\) truy vấn, mỗi truy vấn gồm hai số nguyên \(L, R\).

Yêu cầu: Cho \(n, s_1, s_2, \dots, s_n\) và \(q\). Ứng với mỗi truy vấn, hãy đếm số lượng mã nghi vấn trong dãy \(s_L, s_{L+1}, \dots, s_R\).

Input

• Dòng 1 ghi hai số nguyên \(n\) và \(q\) (\(1 \le n \le 10^5; 1 \le q \le 5 \cdot 10^3\)).
• Dòng 2 ghi \(n\) mã đuôi \(s_1, s_2, \dots, s_n\).
• \(q\) dòng tiếp theo, mỗi dòng ghi hai số nguyên \(L, R\) (\(1 \le L \le R \le n\)), biểu diễn một truy vấn.

Output

• Ghi ra \(q\) dòng, dòng thứ \(i\) (\(1 \le i \le q\)) ghi một số nguyên là số lượng mã nghi vấn ứng với truy vấn \(i\).

Example

8 4
2556 2229 0006 2112 9129 2002 0116 1236
1 4
2 8
5 7
4 8

3
4
2
3

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(q = 1\).
• Subtask \(2\) (\(10\%\) số điểm): \(n \le 10^3; q \le 10^3\).
• Subtask \(3\) (\(80\%\) số điểm): Không có ràng buộc gì thêm.