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 ≤ 1 000 000 000$
* $1 ≤ Q ≤ 100 000$
* *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

* $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

h2. Precizări

* Pentru teste in valoare de 10 de puncte:
** $1 ≤ A ≤ B ≤ 1 000$
** $1 ≤ Q ≤ 1 000$
* Pentru teste in valoare de 10 de puncte:
** $1 ≤ A ≤ B ≤ 1 000 000 000$
** $1 ≤ Q ≤ 1 000$
* Pentru teste in valoare de 20 de puncte:
** $1 ≤ A ≤ B ≤ 1 000 000$
** $1 ≤ Q ≤ 100 000$
* Pentru teste in valoare de 30 de puncte:
** $1 ≤ A ≤ B ≤ 1 000 000 000$
** $1 ≤ Q ≤ 100 000$

 
* Pentru teste in valoare de $5$ puncte:
** $1 ≤ A ≤ B ≤ 10^2^$
** $1 ≤ Q ≤ 10^3^$
* Pentru alte teste in valoare de $5$ puncte:
** $1 ≤ A ≤ B ≤ 10^3^$
** $1 ≤ Q ≤ 10^3^$
* Pentru alte teste in valoare de $15$ puncte:
** $1 ≤ A ≤ B ≤ 10^9^$
** $1 ≤ Q ≤ 10^3^$
* Pentru alte teste in valoare de $15$ puncte:
** $1 ≤ A ≤ B ≤ 10^6^$
** $1 ≤ Q ≤ 10^5^$
* Pentru alte teste in valoare de $20$ de puncte:
** $1 ≤ A ≤ B ≤ 10^9^$
** $1 ≤ Q ≤ 10^5^$

h2. Exemplu