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

Cătălin şi-a făcut, ca tot românul, provizii pentru criza ce urmează. Acesta are acum o cantitate suficientă (“fără număr”) din fiecare tip de bancnota. In Alexandria, oraşul în care locuieşte, se folosesc doar bancnote care au valoarea egală cu un număr prim. El numeşte un număr “as” dacă este o putere a unei bancnote şi pune pariu pe toţi banii lui ca nu puteţi răspunde la Q întrebări de forma: "Câţi aşi sunt în intervalul [A, B]?".
Încercaţi să răspundeţi la întrebările lui Cătălin pentru a câştiga pariul.

Date de intrare

Fişierul de intrare asi.in conţine pe prima linie un număr natural Q reprezentând numărul de întrebări. Pe următoarele Q linii se găsesc câte 2 numere A şi B, reprezentând capetele intervalului din întrebarea Q.

Date de ieşire

În fişierul de ieşire asi.out se vor afla Q numere cu răspunsul, în ordine, la cele Q întrebări.

Restricţii

• 1 ≤ Q ≤ 100 000
• 1 ≤ A ≤ B ≤ 1 000 000 000
• Cătălin de la Alexandria considera un număr "as" dacă poate fi scris ca pⁱ unde p este prim şi i ≥ 2

Precizări

• 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 şi 20 singurele numere care respecta regula sunt 8 = 2³, 9 = 3² şi 16 = 2⁴.

Cum se trimit solutii?