asi

Asi

h2. 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.

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.

h2. 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.

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

h2. Restricţii
* $1 ≤ A ≤ B ≤ 10^12^$
* $1 ≤ Q ≤ 10^5^$

* *Cătălin de la Alexandria considera un număr "as" dacă poate fi scris ca p^i^ unde p este prim şi i ≥ 2*
* 1 nu este considerat numar prim

* Cătălin de la Alexandria considera un număr "as" dacă poate fi scris ca p^i^ unde p este prim şi i ≥ 2
* $1$ nu este considerat numar prim

h2. Precizări

* Pentru teste in valoare de 5 puncte:

* Pentru teste in valoare de $5$ puncte:

** $1 ≤ A ≤ B ≤ 10^2^$

** $1 ≤ Q ≤ 1^3^$
* Pentru teste in valoare de 5 puncte:

** $1 ≤ Q ≤ 10^3^$
* Pentru alte teste in valoare de $5$ puncte:

** $1 ≤ A ≤ B ≤ 10^3^$

** $1 ≤ Q ≤ 1^3^$
* Pentru teste in valoare de 15 puncte:

** $1 ≤ Q ≤ 10^3^$
* Pentru alte teste in valoare de $15$ puncte:

** $1 ≤ A ≤ B ≤ 10^9^$

** $1 ≤ Q ≤ 1 000$
* Pentru teste in valoare de 15 puncte:

** $1 ≤ Q ≤ 10^3^$
* Pentru alte teste in valoare de $15$ puncte:

** $1 ≤ A ≤ B ≤ 10^6^$
** $1 ≤ Q ≤ 10^5^$

* Pentru teste in valoare de 20 de puncte:

* Pentru alte teste in valoare de $20$ de puncte:

** $1 ≤ A ≤ B ≤ 10^9^$
** $1 ≤ Q ≤ 10^5^$