An là một thành viên tích cực của FYT. Nhờ tinh thần trách nhiệm và hoàn thành tốt công việc chuyên môn, An được các bạn nữ xinh đẹp trong FYT yêu quý. Trong đợt tuyển sinh của FYT lần này, An là người phụ trách ra đề chuyên môn. An đã nghĩ ra một bài toán như sau: cho một số nguyên dương gồm các chữ số khác có độ dài là , chữ số thứ có giá trị , hãy kiểm tra xem có tồn tại cách xóa đi đúng chữ số bất kỳ để số đó có chia hết cho hay không? Cảm thấy bài toán quá dễ, An đã khoe với Tâm cách làm. Không ngờ rằng, Tâm lại hỏi ngược lại An: "Vậy em đố anh, bây giờ nếu không phải là chia hết cho mà là chia hết cho thì làm như thế nào?".
Không những thế, Tâm còn hỏi có bao nhiêu cách để tạo ra được số chia hết cho bằng cách xóa đi đúng chữ số bất kỳ. Đến đây thì An cảm thấy hơi choáng váng, nhưng vì không muốn mất mặt với Tâm, An nhất định phải làm được bài toán này. An đã bí mật nhờ các bạn trong cuộc thi FYT Code Cup 2020 giúp đỡ. Các bạn hãy giúp An nhé.
Lưu ý: Gọi là cách tạo ra số mới khi xóa hai chữ số và . Hai cách xóa và được gọi là khác nhau khi và chỉ khi hoặc .
Dữ liệu vào:
Dòng đầu tiên chứa số nguyên dương ;
Dòng thứ hai chứa chữ số liên tiếp nhau , các chữ số nằm trong đoạn .
Dữ liệu ra:
Một số nguyên không âm duy nhất tương ứng với số cách xóa đi hai chữ số để số mới tạo thành chia hết cho .
Ví dụ:
Dữ liệu vào:
5
12121
Dữ liệu ra:
4
Dữ liệu vào:
4
1111
Dữ liệu ra:
6
Dữ liệu vào:
3
111
Dữ liệu ra:
0
Giải thích:
Trong ví dụ thứ nhất, có cách xóa thỏa mãn yêu cầu đề bài là . Cả cách sau khi xóa đều tạo thành số chia hết cho .
Trong ví dụ thứ hai, có cách xóa thỏa mãn yêu cầu đề bài là . Cả cách sau khi xóa đều tạo thành số chia hết cho .
Trong ví dụ thứ ba, không tồn tại cách xóa thỏa mãn yêu cầu đề bài.
