Bình là người đam mê Toán học và thích tìm hiểu về các số có tính chất đặc biệt. Bình gọi số nguyên dương ~X~ là số thú vị nếu hai chữ số tận cùng của ~X~ tạo thành một số chia hết cho số nguyên dương ~k~ cho trước.

Ví dụ, nếu ~k = 12~ thì số 1236 là số thú vị vì hai chữ số cuối là 36 chia hết cho 12. Ngược lại, số 1457 không phải là số thú vị.

Bình muốn đếm số lượng số thú vị trong đoạn ~[a, b]~. Hãy viết chương trình giúp Bình giải quyết bài toán trên.

Yêu cầu: Đưa ra số lượng số thú vị trong đoạn ~[a, b]~.

Input

• Dòng đầu tiên ghi hai số nguyên dương ~T~ và ~k~ (~T \le 10^5, k \le 99~);
• ~T~ dòng tiếp theo, mỗi dòng ghi hai số nguyên dương ~a, b~ (~10^2 \le a \le b \le 10^{18}~).

Output

Ghi ra ~T~ dòng, mỗi dòng tương ứng là số lượng số thú vị trong đoạn ~[a, b]~.

Sample Input 1

2 11
100 200
201 300

Sample Output 1

11
10

Giải thích:

• Từ ~100 \to 200~ có 11 số có 2 chữ số tận cùng chia hết cho 11.
• Từ ~201 \to 300~ có 10 số có 2 chữ số tận cùng chia hết cho 11.

Giới hạn

• 50% số test có ~T = 1, 10^2 \le a \le b \le 10^6~;
• 40% số test có ~T \le 10^5, 10^2 \le a \le b \le 10^6~;
• 10% số test có ~T \le 10^5, 10^2 \le a \le b \le 10^{18}~.

Trong một buổi ngoại khóa của Câu lạc bộ Tin học, giáo viên tổ chức trò chơi tìm "Hộp quà may mắn". Các đội chơi sẽ nhận được một xâu ~S~ chỉ gồm các kí tự số. Mỗi đội phải tìm được mã số của hộp quà may mắn. Mã số cần tìm là số lượng xâu con trong xâu ~S~ tạo thành số đặc biệt. Số đặc biệt là số chia hết cho 97 và có tổng các chữ số chia hết cho 3. Chấp nhận các số có chữ số 0 đứng đầu.

Yêu cầu: Đưa ra số lượng xâu con trong xâu ~S~ tạo thành số đặc biệt là mã số của hộp quà may mắn cần tìm.

Input

Gồm một dòng là xâu ký tự ~S~ có độ dài xâu ~|S| \le 10^5~.

Output

Ghi một dòng ghi số lượng xâu con trong xâu ~S~ tạo thành số đặc biệt.

Sample Input 1

2910

Sample Output 1

3

Giải thích: Có 3 số đặc biệt là 291, 2910, 0.

• 291: 291 chia hết cho 97, tổng chữ số 2+9+1=12 chia hết cho 3.
• 2910: 2910 chia hết cho 97, tổng chữ số 2+9+1+0=12 chia hết cho 3.
• 0: 0 chia hết cho 97, tổng chữ số 0 chia hết cho 3.

Giới hạn

• 50% số test ứng với độ dài xâu ~|S| \le 300~;
• 30% số test ứng với độ dài xâu ~|S| \le 10^3~;
• 20% số test ứng với độ dài xâu ~|S| \le 10^5~.

Thành phố A đang quy hoạch xây dựng đô thị kiểu mẫu với các tiêu chuẩn "xanh, sạch, đẹp, hiện đại", trong đó có dự án sơn các ngôi nhà liền kề trên cùng một trục đường để có màu sắc giống nhau, với chi phí cho phép là ~k~. Hiện tại mỗi ngôi nhà được sơn với một màu và mỗi màu sơn được biểu diễn bằng một ký tự từ 'a' đến 'z'. Chi phí chuyển đổi màu sơn của ngôi nhà từ màu sơn ~x~ sang màu sơn ~y~ là khoảng cách từ vị trí ký tự biểu diễn màu sơn ~x~ đến vị trí ký tự biểu diễn màu sơn ~y~ trong bảng mã ASCII.

Ví dụ: Chi phí chuyển đổi từ màu sơn biểu diễn bằng ký tự 'a' sang màu sơn biểu diễn bằng ký tự 'b' là ~|97 - 98| = 1~.

Hãy viết chương trình giúp ban quản lý quy hoạch đô thị giải quyết dự án trên.

Yêu cầu: Đưa ra số lượng nhiều nhất các ngôi nhà liền kề cùng màu sơn sau khi thực hiện dự án, với tổng chi phí chuyển đổi không vượt quá ~k~.

Input

• Dòng đầu tiên ghi số nguyên dương ~k~ (~k \le 10^5~) là chi phí cho phép của dự án;
• Dòng thứ hai ghi xâu ký tự ~S~ có độ dài xâu ~|S| \le 5 \times 10^5~ là xâu biểu diễn màu sơn hiện tại của các ngôi nhà.

Output

Ghi ra một dòng duy nhất là kết quả cần tìm.

Sample Input 1

2
babac

Sample Output 1

4

Giải thích: Ta thực hiện biến đổi ký tự 'b' -> 'a' (hoặc 'a' -> 'b') và thu được xâu mới 'aaaac' (hoặc 'bbbbc'). Tổng chi phí biến đổi là 2. Số lượng nhiều nhất các ngôi nhà liền kề cùng màu sơn là 4.

Sample Input 2

2
afab

Sample Output 2

2

Giải thích: Ta thực hiện biến đổi ký tự 'b' -> 'a' (hoặc 'a' -> 'b') và thu được xâu mới 'afaa' (hoặc 'afbb'). Tổng chi phí biến đổi là 1. Số lượng nhiều nhất các ngôi nhà liền kề cùng màu sơn là 2.

Giới hạn

• 60% số test có độ dài xâu ~|S| \le 10^3~;
• 40% số test có độ dài xâu ~|S| \le 5 \times 10^5~.

Bố bạn Hùng là một nhà đầu tư trong một quỹ tài chính. Chiến lược đầu tư của bố bạn là chọn đúng ~k~ thời điểm để đầu tư chuỗi dữ liệu của thị trường gồm ~n~ ngày. Mỗi ngày có một chỉ số thị trường là ~a_i~. Bố bạn đã xây dựng một chiến lược phân bổ trọng số ~w_1, w_2, ..., w_k~ tương ứng với từng lần đầu tư. Hùng mong muốn giúp bố của mình lựa chọn ~k~ ngày khác nhau (theo đúng thứ tự thời gian) để đầu tư cho tổng lợi nhuận ~S~ đạt cao nhất có thể theo công thức: ~S = w_1 \times a_{t_1} + w_2 \times a_{t_2} + ... + w_k \times a_{t_k}~. Ngoài ra, bạn cũng muốn biết có bao nhiêu cách chọn ngày để đạt được tổng lợi nhuận lớn nhất đó.

Yêu cầu: Tìm tổng lợi nhuận lớn nhất và số cách đầu tư để đạt được tổng lợi nhuận lớn nhất đó.

Input

• Dòng đầu tiên ghi hai số nguyên dương ~n, k~ (~n \le 10^5, k \le 100, k \le n~);
• Dòng thứ hai ghi ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~a_i \le 10^9~);
• Dòng thứ ba ghi ~k~ số nguyên ~w_1, w_2, ..., w_k~ (~|w_i| \le 10^6~).

Output

Ghi ra hai dòng, dòng thứ nhất ghi tổng lợi nhuận lớn nhất và dòng thứ hai ghi số cách đầu tư để đạt được tổng lợi nhuận lớn nhất đó. Kết quả được lấy dư cho ~10^9 + 7~.

Sample Input 1

5 3
2 8 6 3 3
5 2 6

Sample Output 1

70
2

Giải thích: Có 2 cách chọn các ngày là: ngày thứ {2, 3, 4} hoặc ngày thứ {2, 3, 5} đều cho tổng lợi nhuận là: ~5 \times 8 + 2 \times 6 + 6 \times 3 = 40 + 12 + 18 = 70~.

Giới hạn

• 20% số test: ~0 < n \le 10^2, k = 1~;
• 40% số test: ~0 < n \le 10^3, 0 < k \le 100~;
• 40% số test: ~0 < n \le 10^5, 0 < k \le 100~.