Fişierul intrare/ieşire:	asi.in, asi.out	Sursă	FMI No Stress 9 Warmup
Autor	Mihai-Dragos Preda, Stefan Radu	Adăugată de	FMI No Stress 9 •fminostress9
Timp execuţie pe test	0.175 sec	Limită de memorie	32768 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Asi

Catalin si-a facut, ca tot romanul, provizii pentru criza ce urmeaza. Acesta are acum o cantitate suficienta (“fara numar”) din fiecare tip de bancnota. In Alexandria, orasul in care locuieste, se folosesc doar bancnote care au valoarea un numar prim. El numeste un numar “as” daca este o putere a unei bancnote si pune pariu pe toti banii lui ca nu puteti raspunde la Q intrebari de forma: "Cati asi sunt in intervalul [A, B]?"
Calculati cate numere din intervalele date sunt puteri ale unui numar prim si castigati pariul.

Date de intrare

Fişierul de intrare asi.in contine pe prima linie un numar natural Q reprezentand numarul de intrebari. Pe urmatoarele Q linii se gasesc cate 2 numere A si B, reprezentand capetele intervalului din intrebarea Q.

Date de ieşire

În fişierul de ieşire asi.out se vor afla Q numere cu raspunsul, in ordine, la cele Q intrebari.

Restricţii

• 1 ≤ Q ≤ 100 000
• 1 ≤ A ≤ B ≤ 1 000 000 000
• Catalin de la Alexandria considera un numar "as" daca poate fi scris ca pⁱ unde p este prim si i ≥ 2

Precizari

• pentru teste in valoare de 10 de puncte:
  • 1 ≤ A ≤ B ≤ 100
  • 1 ≤ Q ≤ 1 000
• pentru teste in valoare de 10 de puncte:
  • 1 ≤ A ≤ B ≤ 1 000
  • 1 ≤ Q ≤ 1 000
• pentru teste in valoare de 20 de puncte:
  • 1 ≤ A ≤ B ≤ 1 000 000 000
  • 1 ≤ Q ≤ 1 000
• pentru teste in valoare de 30 de puncte:
  • 1 ≤ A ≤ B ≤ 1 000 000
  • 1 ≤ Q ≤ 100 000

Exemplu

Explicaţie

Intre 7 si 20 singurele numere care respecta regula sunt 8 = 2³, 9 = 3² si 16 = 2⁴.

Cum se trimit solutii?