== include(page="template/taskheader" task_id="puteri4") ==

Poveste şi cerinţă...

Nu e un secret pentru nimeni faptul că Mireluş se antrenează în timpul liber cu probleme de algoritmică. De curând a aflat că un număr natural N, pentru care există două numere naturale nenule A şi B (B>1) astfel încât N = A^B^, se numeşte putere. Mireluş şi-a propus să determine numărul de puteri din intervalul [X, Y], unde X şi Y sunt numere naturale nenule.
Cum probabil v-aţi imaginat deja, Mireluş nu a reuşit să rezolve această problemă şi a decis să ceară ajutorul Olimpiei D’Info. Pentru a fi sigur că nici ea nu greşeşte, i-a dat un set de intervale şi i-a cerut să determine pentru fiecare interval numărul de puteri corespunzător.
 
h2. Cerinta
 
Dându-se numărul de intervale T şi pentru fiecare dintre cele T intervale cele două extremităţi, determinaţi numărul de puteri corespunzător fiecărui interval dat de Mireluş Olimpiei.

h2. Date de intrare

Fişierul de intrare $puteri4.in$ ...

Fişierul de intrare puteri.in conţine pe prima linie numărul de intervale T, iar pe fiecare dintre următoarele T linii câte 2 numere naturale nenule X Y, separate prin exact un spaţiu, reprezentând extremităţile intervalelor.

h2. Date de ieşire

În fişierul de ieşire $puteri4.out$ ...

Fişierul de ieşire puteri.out va conţine T linii. Pe linia i va fi scris numărul de puteri care aparţin celui de al i-lea interval din fişierul de intrare.

h2. Restricţii

* $... ≤ ... ≤ ...$

* 1 ≤ T ≤ 131
* 1 ≤ X ≤ Y ≤ 10^18^
* Intervalul [X, Y] conţine şi numerele X şi Y.

h2. Exemplu
table(example). |_. puteri4.in |_. puteri4.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 1
| 1 36

|
h3. Explicaţie

...

Cele 9 numere sunt:
1, 4, 8, 9, 16, 25, 27, 32, 36

== include(page="template/taskfooter" task_id="puteri4") ==