## Prime queries

Points: 35 (partial)
Time limit: 1.5s
Memory limit: 250M

Author:
Problem type

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