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* &gt; 0, *p* &gt; 1 such that *x* = *a*<sup class="upper-index">*p*</sup>.
The first line contains the number of queries *Q* (1 ≤ *Q* ≤ 10<sup class="upper-index">5</sup>).

The next *Q* lines contains two integers *L*, *R* each (1 ≤ *L* ≤ *R* ≤ 10<sup class="upper-index">18</sup>).
In query one the suitable numbers are 1 and 4.
6
1 4
9 9
5 7
12 29
137 591
1 1000000
2
1
0
3
17
1111
20
862 928
758 964
541 789
622 943
328 900
14 764
217 972
461 847
442 468
900 986
518 529
938 993
549 851
690 944
484 601
320 910
98 868
816 915
765 880
551 770
1
4
5
6
14
32
20
9
0
2
1
1
6
4
4
15
26
2
2
4
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
using namespace std;

#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define REP2(i,n) for(int i=0;i<(int)(n);i++)
#define REP3(i,m,n) for(int i=m;i<(int)(n);i++)
#define REP4(i,m,n,s) for(int i=m;(s>0 and i<(int)(n)) or (s<0 and i>(int)(n));i+=s)
#define REP(...) GET_MACRO(__VA_ARGS__, REP4, REP3, REP2)(__VA_ARGS__)
#define REPIT(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define PIS(x) printf("%d ",x)
#define PN() putchar('\n')
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define MT make_tuple

using PII = pair<int, int>;
using TI3 = tuple<int, int, int>;
using LL = long long;
using ULL =  unsigned long long;
using MAT = array<array<LL, 2>, 2>;

template<class T> void _read( T &x ) { cin>>x; }
void _read(int &x) { scanf("%d", &x); }
void _read(LL &x) { scanf("%lld", &x); }
void _read(double &x) { scanf("%lf", &x); }
void _read(char &x) { scanf(" %c", &x); }
void _read(char *x) { scanf("%s", x); }
void read() {}
template<class T, class... U>
void read( T& head, U&... tail ) {
    _read(head);
    read(tail...);
}

template<class T> void _print( const T &x ) { cout << x; }
void _print( const int &x ) { printf("%d", x); }
void _print( const LL &x ) { printf("%lld", x); }
void _print( const double &x ) { printf("%.16lf",x); }
void _print( const char &x ) { putchar(x); }
void _print( const char *x ) { printf("%s",x); }
template<class T> void _print( const vector<T> &x ) { for (auto i = x.begin(); i != x.end(); _print(*i++)) if (i != x.cbegin()) putchar(' '); }
void print() {}
template<class T, class... U> void print( const T& head, const U&... tail ) {
    _print(head);
    putchar(sizeof...(tail) ? ' ' : '\n');
    print(tail...);
}

const int MOD = 1000000007;
#define MAX_N 300005

vector<int> p1 = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 30, 42};
vector<int> p2 = {6, 10, 14, 22, 26, 34, 38, 46, 58, 15, 21, 33, 39, 51, 57, 35, 55};

long long mypow(long long x, long long p) {
    long long ret = 1;
    while(p) {
        if(p & 1) {
            ret = ret * x;
        }
        x = x * x;
        p >>= 1;
    }
    return ret;
}

LL count(double n, int p) {
    LL x = exp(log(n + min(n / 1000, 1.)) / p);
    return x;
}

LL solve(LL n) {
    if(n == 0) {
        return 0;
    }
    LL ans = 0;
    vector<LL> x;
    REPIT(ii, p1) {
        ans += count(n, *ii) - 1;
    }
    REPIT(ii, p2) {
        ans -= count(n, *ii) - 1;
    }
    return ans + 1;
}

int main()
{
    int Q;
    read(Q);
    REP(i, Q) {
        LL L, R;
        read(L, R);
        print(solve(R) - solve(L - 1));
    }
    return 0;
}
