h2. Restricţii

* $1 ≤ A ≤ B ≤ 1 000 000 000$
* $1 ≤ Q ≤ 100 000$

* $1 ≤ A ≤ B ≤ 10^12^$
* $1 ≤ Q ≤ 1^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$

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

** $1 ≤ Q ≤ 1 000$

* Pentru teste in valoare de 15 puncte:
** $1 ≤ A ≤ B ≤ 10^6^$
** $1 ≤ Q ≤ 10^5^$

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

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

h2. Exemplu