## Prime queries

You are given a list of integers \(a_i\) and you are asked to answer \(q\) queries.

Each query is of the form \(l_i\), \(r_i\) and asks you to count for each prime number \(p, p \in [l_i, r_i]\) the number of integers \(a_i\) that are multiples of \(p\) and output their sum (the sum of counts, not the sum of multiples !).

#### Input Specification

The first line of the input file contains three integers \(n\) the number of elements \(a_i\) , \(k\) the maximum range and Q the number of queries (\(1 \leq n,k,q \leq 10^6\)).

Then follows one line containing \(n\) integers \(a_i\) (\(1 \leq a_i \leq 10^6\)).

\(Q\) lines will follow, each line consists of two integers \(l_i\) \(r_i\) (\(1 \leq l_i \leq r_i \leq k\)).

#### Output Specification

For each query output one integer containing the answer to the problem.

#### Scoring

- \(n, q, k \leq 10^2\) (20 points).
- \(q = 1, n \leq 10^3\) (20 points).
- \(q = 1\) (30 points).
- No additional constraints (30 points).

#### Sample Input

```
3 10 4
6 7 8
1 2
1 3
5 6
1 10
```

#### Sample Output

```
2
3
0
4
```

## Comments