Fişierul intrare/ieşire:asi.in, asi.outSursăFMI No Stress 9 Warmup
AutorMihai-Dragos Preda, Stefan RaduAdăugată defminostress9FMI No Stress 9 fminostress9
Timp execuţie pe test0.175 secLimită de memorie32768 kbytes
Scorul tăuN/ADificultateN/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 mai mare strict ca 1 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 intervalelor.

Date de ieşire

În fişierul de ieşire asi.out se vor afla Q linii, fiecare conţinând răspunsul la întrebarea aferentă.

Restricţii

  • 1 ≤ A ≤ B ≤ 1012
  • 1 ≤ Q ≤ 105
  • Cătălin de la Alexandria considera un număr "as" dacă poate fi scris ca pi unde p este prim şi i ≥ 2
  • 1 nu este considerat numar prim

Precizări

  • Pentru teste in valoare de 5 puncte:
    • 1 ≤ A ≤ B ≤ 102
    • 1 ≤ Q ≤ 103
  • Pentru alte teste in valoare de 5 puncte:
    • 1 ≤ A ≤ B ≤ 103
    • 1 ≤ Q ≤ 103
  • Pentru alte teste in valoare de 15 puncte:
    • 1 ≤ A ≤ B ≤ 109
    • 1 ≤ Q ≤ 103
  • Pentru alte teste in valoare de 15 puncte:
    • 1 ≤ A ≤ B ≤ 106
    • 1 ≤ Q ≤ 105
  • Pentru alte teste in valoare de 20 de puncte:
    • 1 ≤ A ≤ B ≤ 109
    • 1 ≤ Q ≤ 105

Exemplu

asi.inasi.out
1
7 20
3

Explicaţie

Intre 7 şi 20 singurele numere care respecta regula sunt 8 = 23, 9 = 32 şi 16 = 24.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?