#include <bits/stdc++.h>
using namespace std;
const vector<int> p{2,  3,  5,  7,  11, 13, 17, 19, 23,
                    29, 31, 37, 41, 43, 47, 53, 59};
const vector<int> p2{6,  10, 14, 15, 21, 22, 26, 33, 34,
                     35, 38, 39, 46, 51, 55, 57, 58};
const vector<int> p3{30, 42};
vector<vector<long long int>> my_pow(60);
map<long long int, long long int> m;
long long int solve2(long long int n, long long int x) {
  if (n == 2) {
    long long int lo = 0, hi = 1e9 + 1;
    while (lo < hi - 1) {
      long long int mid = (lo + hi) / 2;
      if (mid * mid > x) {
        hi = mid;
      } else {
        lo = mid;
      }
    }
    return lo;
  } else {
    int lo = 0, hi = my_pow[n].size() - 1;
    while (lo < hi - 1) {
      int mid = (lo + hi) / 2;
      if (my_pow[n][mid] > x) {
        hi = mid;
      } else {
        lo = mid;
      }
    }
    return lo;
  }
}
void init(const vector<int>& v) {
  for (auto x : v) {
    if (x == 2) continue;
    for (int i = 0;; ++i) {
      long long int res = 1;
      for (int j = 0; j < x; ++j) {
        res *= i;
        if (res > 1e18) {
          break;
        }
      }
      my_pow[x].push_back(res);
      if (res > 1e18) break;
    }
  }
}
long long int solve(long long int x) {
  if (x == 0) {
    return 0;
  } else if (x < 4) {
    return 1;
  }
  if (m.find(x) != m.end()) return m[x];
  long long int ret = 1;
  for (int i = 0; i < p.size(); ++i) {
    ret += solve2(p[i], x) - 1;
  }
  for (int i = 0; i < p2.size(); ++i) {
    ret -= solve2(p2[i], x) - 1;
  }
  for (int i = 0; i < p3.size(); ++i) {
    ret += solve2(p3[i], x) - 1;
  }
  m[x] = ret;
  return ret;
}
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  init(p);
  init(p2);
  init(p3);
  int Q;
  cin >> Q;
  while (Q--) {
    long long int L, R;
    cin >> L >> R;
    cout << solve(R) - solve(L - 1) << endl;
  }
  return 0;
}
