#include <bits/stdc++.h>
using namespace std;
bool binaria(long long int x, long long int y, long long int num) {
  long long int m;
  if (x == y) {
    if (x * x == num) {
      return true;
    } else {
      return false;
    }
  } else {
    if (y == x + 1) {
      if (x * x == num) {
        return true;
      } else {
        if (y * y == num) {
          return true;
        } else {
          return false;
        }
      }
    } else {
      m = (x + y) / 2;
      if (m * m < num) {
        return binaria(m + 1, y, num);
      } else {
        return binaria(x, m, num);
      }
    }
  }
}
long long int binaria2(long long int x, long long int y, long long int l) {
  long long int m;
  if (x == y) {
    return x;
  } else {
    if (y == x + 1) {
      if (y * y <= l) {
        return y;
      } else {
        return x;
      }
    } else {
      m = (x + y) / 2;
      if (m * m <= l) {
        return binaria2(m, y, l);
      } else {
        return binaria2(x, m - 1, l);
      }
    }
  }
}
long long int binaria3(long long int x, long long int y, long long int r) {
  long long int m;
  if (x == y) {
    return x;
  } else {
    if (y == x + 1) {
      if (x * x >= r) {
        return x;
      } else {
        return y;
      }
    } else {
      m = (x + y) / 2;
      if (m * m >= r) {
        return binaria3(x, m, r);
      } else {
        return binaria3(m + 1, y, r);
      }
    }
  }
}
vector<long long int> vec, vec2;
long long int binaria4(long long int x, long long int y, long long int l) {
  long long int m;
  if (x == y) {
    return x;
  } else {
    if (y == x + 1) {
      if (vec2[y] <= l) {
        return y;
      } else {
        return x;
      }
    } else {
      m = (x + y) / 2;
      if (vec2[m] <= l) {
        return binaria4(m, y, l);
      } else {
        return binaria4(x, m - 1, l);
      }
    }
  }
}
long long int binaria5(long long int x, long long int y, long long int r) {
  long long int m;
  if (x == y) {
    return x;
  } else {
    if (y == x + 1) {
      if (vec2[y] <= r) {
        return y;
      } else {
        return x;
      }
    } else {
      m = (x + y) / 2;
      if (vec2[m] <= r) {
        return binaria5(m, y, r);
      } else {
        return binaria5(x, m - 1, r);
      }
    }
  }
}
int cont[26];
int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  long long int i, j, q, l, r, tope, rev, cuadradosup, cuadradoinf, liminf,
      limsup, cuadrados, resto;
  cuadrados = 0;
  tope = 1;
  for (i = 0; i < 18; i++) tope = tope * 10;
  bool checa;
  vec.push_back(0);
  for (i = 2; i <= 1000000; i++) {
    checa = binaria(1, 1000000, i);
    if (checa == false) {
      j = i * i * i;
      while (j <= tope) {
        vec.push_back(j);
        rev = tope / j + 1;
        if (i * i <= rev) {
          j = j * i * i;
        } else {
          break;
        }
      }
    }
  }
  sort(vec.begin(), vec.end());
  for (i = 0; i < vec.size(); i++) {
    j = i;
    vec2.push_back(vec[j]);
    bool checa2 = false;
    while (checa2 == false) {
      if (j >= vec.size()) {
        checa2 = true;
        i = j;
      } else {
        if (vec[j] == vec[i]) {
          j++;
        } else {
          i = j - 1;
          checa2 = true;
        }
      }
    }
  }
  cin >> q;
  for (i = 0; i < q; i++) {
    cin >> l >> r;
    cuadrados = 0;
    resto = 0;
    cuadradoinf = binaria2(1, 1000000000, l);
    cuadradosup = binaria3(1, 1000000000, r);
    if (cuadradoinf * cuadradoinf != l) cuadradoinf++;
    if (cuadradosup * cuadradosup != r) cuadradosup--;
    liminf = binaria4(0, vec2.size() - 1, l);
    limsup = binaria4(0, vec2.size() - 1, r);
    if (cuadradosup - cuadradoinf + 1 > 0)
      cuadrados = cuadradosup - cuadradoinf + 1;
    if (vec2[liminf] != l) liminf++;
    if (limsup - liminf + 1 > 0) resto = limsup - liminf + 1;
    cout << resto + cuadrados << "\n";
  }
}
