== include(page="template/taskheader" task_id="puteri4") ==
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.
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.
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 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.
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
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.
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$
* 1 ≤ T ≤ 131
* 1 ≤ X ≤ Y ≤ 10^18^
* Intervalul [X, Y] conţine şi numerele X şi Y.
h3. Exemplu
h2. Exemplu
table(example). |_. puteri4.in |_. puteri4.out |
| 1
1 36
| 9
| 1 36
|
h3. Explicaţie
