#include <bits/stdc++.h>
using namespace std;
vector<int> v1 = {2,  3,  5,  7,  11, 13, 17, 19, 23,
                  29, 31, 37, 41, 43, 47, 53, 59};
vector<int> v2;
vector<int> v3;
class Solution {
 public:
  int getRoot(long long N, int k) {
    int t = pow((long double)N + 0.5, 1.0 / k);
    return t;
  }
  long long calcFor(long long N) {
    if (N == 0) return 0;
    long long sum = 1;
    for (auto v : v1) sum += getRoot(N, v) - 1;
    for (auto v : v2) sum -= getRoot(N, v) - 1;
    for (auto v : v3) sum += getRoot(N, v) - 1;
    return sum;
  }
  void solve(std::istream& in, std::ostream& out) {
    long long L, R;
    scanf("%I64d%I64d", &L, &R);
    printf("%I64d\n", (calcFor(R) - calcFor(L - 1)));
  }
};
void solve(std::istream& in, std::ostream& out) {
  for (int i = 0; i < v1.size(); i++) {
    for (int j = i + 1; j < v1.size(); j++) {
      if (v1[i] * v1[j] > 60) break;
      v2.push_back(v1[i] * v1[j]);
      for (int k = j + 1; k < v1.size(); k++) {
        if (v1[i] * v1[j] * v1[k] > 60) break;
        v3.push_back(v1[i] * v1[j] * v1[k]);
      }
    }
  }
  out << std::setprecision(12);
  Solution solution;
  int Q;
  scanf("%d", &Q);
  while (Q--) solution.solve(in, out);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  istream& in = cin;
  ostream& out = cout;
  solve(in, out);
  return 0;
}
