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

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 este insa un programator incepator si va roaga sa il ajutati sa raspunda repede 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 'teorema 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 si a decis sa investigheze problema prin metode normale, folosind calculatorul (pentru ca nu stie matematica). Dubota este insa un programator incepator si va roaga sa il ajutati sa raspunda repede la $Q$ intrebari de tipul: Cate numere prime sunt intre $a$ si $b$, unde $a, b ≤ N$.

h2. Date de intrare

3481