== 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$.
* Pentru $10%$ din teste $Y ≤ 5.000$
* Pentru alte $25%$ din teste $Y ≤ 100.000$
* Pentru alte $20%$ din teste $Y ≤ 10.000.000$
h2. Exemplu
h3. 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
| 9
|
h3. Explicaţie
...
Cele 9 numere sunt:
1, 4, 8, 9, 16, 25, 27, 32, 36
== include(page="template/taskfooter" task_id="puteri4") ==
