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 !).
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\)).
For each query output one integer containing the answer to the problem.
- \(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).
3 10 4 6 7 8 1 2 1 3 5 6 1 10
2 3 0 4