Puteri

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.

Cerință

Dându-se numărul de intervale $T$ şi pentru fiecare din cele $T$ intervale cele două extremităţi, determinaţi numărul de puteri corespunzător fiecărui interval dat de Mireluş Olimpiei.

Date de intrare

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

Date de ieșire

Fișierul de ieșire puteri.out conţine $T$ linii. Fiecare linie va conţine numărul de puteri care aparţin intervalului corespunzător din fişierul de intrare.

Restricții și precizări

• $1 \leq T \leq 131$
• $1 \leq X \leq Y \leq 10^{18}$
• Intervalul $[X, Y]$ conţine şi numerele $X$ şi $Y$.
• Pentru $10\%$ din teste $Y \leq 5 \ 000$.
• Pentru alte $25\%$ din teste $Y \leq 100 \ 000$.
• Pentru alte $20\%$ din teste $Y \leq 10 \ 000 \ 000$.

Exemplu

puteri.in

1
1 36

puteri.out

9

Explicație

Cele $9$ numere sunt:

1, 4, 8, 9, 16, 25, 27, 32, 36