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$$.
- 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.
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.
Print he number of special substrings of $$S$$.
- 92, 07, 7, and 72893 are examples of special substrings. These are not the only special substrings in the sample input.
- 728934 is an example of a substring which is not special.
for each input file.
Marks are awarded when all the testcases pass.