Se citesc un numar natural n si un numar natural q, reprezentand numarul de interogari. Urmeaza q linii, fiecare continand doua numere naturale l si r (1 <= l <= r <= n). Pentru fiecare interogare, folosind ciurul lui Eratostene precalculat, determinati cate numere prime exista in intervalul [l, r].
- Date de intrare
- Pe prima linie se afla numarul natural n. Pe a doua linie se afla numarul natural q. Urmeaza q linii, fiecare continand doua numere naturale l si r.
- Date de iesire
- Afiseaza q linii, cate una pentru fiecare interogare, continand numarul de numere prime din intervalul [l, r].
- Restrictii
- 1 <= n <= 100000, 1 <= q <= 50, 1 <= l <= r <= n
Exemple
Exemplul 1
Intrare
20 3 1 20 10 20 1 1
Iesire
8 4 0
Exemplul 2
Intrare
1 1 1 1
Iesire
0