== include(page="template/taskheader" task_id="densitate") ==

Oaia Dubota a invatat de la oaia profesoara despre numerele prime. Profesoara a mai mentionat si ca densitatea numerelor prime este ridicata, aproximativ 1 / ln(N), unde densitatea se masoara intre 1 si N. Asta inseamna ca aproximativ unul din 13 numere sunt prime intre 1 si 500000. Lui Dubota nu ii vine sa creada ca sunt atat de multe numere prime si s-a decis sa investigheze problema. El va roaga sa il ajutati sa raspunda la Q intrebari de tipul: cate numere prime sunt intre a si b?, unde a, b < N.

Oaia Dubota a invatat de la oaia profesoara de matematica despre numerele prime. Pe langa definitia numerelor prime (un numar prim se divide numai cu 1 si cu el insusi), profesoara le-a spus si doua cuvinte despre 'teorama numerelor prime':http://en.wikipedia.org/wiki/Prime_number_theorem. Un rezultat al acestei teoreme este ca aproximativ unul din 13 numere intre 1 si 500000 sunt prime. Lui Dubota nu ii vine sa creada ca sunt atat de multe numere prime si nici nu are inceredere in profesoara (pentru ca aceasta e o oaie) si a decis sa investigheze problema prin metode normale, folosind calculatorul (pentru ca nu stie matematica). Dubota insa este un programator incepator si va roaga sa il ajutati sa raspunda la $Q$ intrebari de tipul: Cate numere prime sunt intre $a$ si $b$, unde $a$, $b$ < $N$.

h2. Date de intrare

Fişierul de intrare $densitate.in$ va contine pe prima linie N si Q. Pe urmatoarele Q linii se afla cate 2 numere a{~i~}, b{~i~} cu semnificatia din enunt.

Fişierul de intrare $densitate.in$ va contine pe prima linie $N$ si $Q$. Pe urmatoarele $Q$ linii se afla cate 2 numere $a{~i~}$, $b{~i~}$ cu semnificatia din enunt.

h2. Date de ieşire

În fişierul de ieşire $densitate.out$ se scrie Q linii, pe care sunt afisate, in ordine, raspunsurile intrebarilor lui Dubota.

În fişierul de ieşire $densitate.out$ se scrie $Q$ linii, pe care sunt afisate, in ordine, raspunsurile intrebarilor lui Dubota.

h2. Restricţii