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~ ~\left(1 \le i \le n\right)~ 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, \ldots, 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}, \ldots, s_R~.

Input

Từ tệp văn bản CAU5.INP:

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

Output

Ghi vào tệp văn bản CAU5.OUT gồm ~q~ dòng:

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

Ràng buộc

• 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.

Ví dụ

Input

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

Output

3
4
2
3

Giải thích

Các mã nghi vấn trong danh sách đã cho là: ~2556, 0006, 2112, 2002, 0116~;

• Truy vấn ~1~, xét các phần tử từ ~1~ đến ~4~, có ~3~ mã nghi vấn là ~2556, 0006, 2112~;
• Truy vấn ~2~, xét các phần tử từ ~2~ đến ~8~, có ~4~ mã nghi vấn là ~0006, 2112, 2002, 0116~;
• Truy vấn ~3~, xét các phần tử từ ~5~ đến ~7~, có ~2~ mã nghi vấn là ~2002, 0116~;
• Truy vấn ~4~, xét các phần tử từ ~4~ đến ~8~, có ~3~ mã nghi vấn là ~2112, 2002, 0116~.