Sad powers
Description
You're given Q queries of the form (L, R).
For each query you have to find the number of such x that L ≤ x ≤ R and there exist integer numbers a > 0, p > 1 such that x = ap.
The first line contains the number of queries Q (1 ≤ Q ≤ 105).
The next Q lines contains two integers L, R each (1 ≤ L ≤ R ≤ 1018).
Output Q lines — the answers to the queries.
Input
The first line contains the number of queries Q (1 ≤ Q ≤ 105).
The next Q lines contains two integers L, R each (1 ≤ L ≤ R ≤ 1018).
Output
Output Q lines — the answers to the queries.
6<br>1 4<br>9 9<br>5 7<br>12 29<br>137 591<br>1 1000000<br>
2<br>1<br>0<br>3<br>17<br>1111<br>
Note
In query one the suitable numbers are 1 and 4.