Two positive integers are said to be relatively prime if their greatest common divisor is equal to 1. You will be given a string of digits S and an integer M. We call a substring, T, of S special if T and M are relatively prime. Your task is to count the number of special substrings of S.

Notes:

• A substring of S is a contiguous segment of S (the entire string counts as a substring too).
• Special substrings are allowed to have any number of leading zeros and they count as distinct special substrings.
• In this problem, a substring is to be interpreted as an integer.

Input:

The first line contains two integers: N \((1 \le N \le 10^3)\), the length of the string and an integer M \((1 \le M \le 10^9)\). The second line contains a string S of length N. You can safely assume that S contains digits only.

Output:

Print he number of special substrings of S.