#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const long long INF = 0x7FFFFFFFFFFFFFFF >> 1;
const long long e = 2.71828182845904523536028747135;
bool is_s(long double x) {
  long long temp = round(pow(10, log10(x) / 2.0));
  return temp * temp == x;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long q;
  cin >> q;
  std::set<long long> s;
  for (long long i = 2; i < 1000010; i++) {
    if (is_s(i)) continue;
    if (s.find(i) != s.end()) continue;
    long long temp = i;
    while ((long double)temp * i * i <= 1000000000000000000) {
      s.insert(temp * i * i);
      temp *= i * i;
    }
  }
  std::vector<long long> v;
  for (auto aa : s) v.push_back(aa);
  while (q--) {
    long long l, r;
    cin >> l >> r;
    cout << fixed << setprecision(0)
         << upper_bound(v.begin(), v.end(), r) -
                lower_bound(v.begin(), v.end(), l) + floor(sqrtl(r)) -
                ceil(sqrt(l)) + 1
         << endl;
  }
  return 0;
}
