Fişierul intrare/ieşire:	densitate.in, densitate.out	Sursă	Algoritmiada 2009, Runda 1
Autor	Stefan Alexandru Filip	Adăugată de	Stefan-Alexandru Filip •Prostu
Timp execuţie pe test	0.15 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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.

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.

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.

Restricţii

• N < 500000
• Q < 100000
• 1 ≤ a ≤ b ≤ N

Exemplu

Cum se trimit solutii?