Count of Substrings Divisible by p

You are given a large number S represented as a string of n digits (possibly with leading zeroes). You are also given a prime number p. There are m queries; each query gives two integers L and R (1-indexed) representing a substring T = S[L...R]. For each query, you need to count the number of nonempty substrings of T that are divisible by p (note that 0 is also considered a multiple of p).

Note:

• If p = 2 or p = 5, a number is divisible by p if and only if its last digit is divisible by p. Thus, in such cases, for a substring T of length L, every ending position i (with 1 ≤ i ≤ L) such that the digit is divisible by p contributes i possible substrings.
• If p is neither 2 nor 5, then since p is coprime with 10, there exists an inverse of 10 modulo p and an efficient method based on prefix sums and modular arithmetic can be used. Define a prefix array P where P[0] = 0 and for i ≥ 0, P[i+1] = (P[i]*10 + digit_i) mod p. Then for a substring S[i...j] the value is divisible by p if and only if \[ P[j+1] \equiv P[i] \times 10^{(j-i+1)} \pmod{p}. \] This condition can be reformulated (using the modular inverse of 10) so that we need to count pairs of indices with equal transformed prefix value. For each query on a substring of S, you can restrict the prefix array to the corresponding segment and count the number of pairs with equal values.

Implement a solution that reads the input, processes each query, and outputs the count for each query.

inputFormat

The input consists of:

1. A line containing the string S (a sequence of digits that may include leading zeros).
2. A line containing the prime number p.
3. A line containing an integer m, the number of queries.
4. m lines each containing two integers L and R (1-indexed), representing the substring S[L...R].

You may assume that 1 ≤ L ≤ R ≤ length(S).

outputFormat

For each query, output a single integer representing the number of substrings of S[L...R] that are divisible by p.

sample

0077
7
1
1 3

6