Two positive integers and are given.
is decimal representation of integer .
Lets define .
For example, if :
For each query you will be given two integers and that define a substring equal to .
Your task is to calculate divisibility of given substring.
Divisibility of given substring is equal to number of pairs such that:
and
is divisible by , assuming that is divisible by any other integer.
Timelimits
Timelimits for this challenge is given here
Input Format
First line contains two integers and separated by a single space. is the number of queries.
Second line contains a big integer .
Next lines contains two integers and separated by a single space each - begin and end points of substring.
Constraints
Output Format
Output lines, the -th line of the output should contain single integer — divisibility of the -th query substring.
Sample Input
3 5
4831318
3 5
5 7
1 7
1 2
2 3
Sample Output
2
3
9
1
1
Explanation
In the first query, b = 3 and e = 5. Two such pairs that are divisible by P = 3 are
f(3, 3) = 3 and f(5, 5). Hence the answer 2.
In the second query, b = 5 and e = 7. Three such pairs that are divisible by P are
F(5, 5) = 3, f(6, 7) = 18 and f(5, 7) = 318