- Prepare
- Data Structures
- Advanced
- Divisibility

# Divisibility

# Divisibility

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