/// 9 = 1 . 9 = 3 . 3
/// => 3^8 có 9 ước
/// 9 . i^2 có 9 ước (i là số nguyên tố)
#include <iostream>
#include <cmath>
using namespace std;

int readInt() {
    int num = 0;
    register char c = getchar();
    while (c != '-' && ('0' > c || '9' < c)) c = getchar();
    bool neg = false;
    if (c == '-') neg = true, c = getchar();
    for(num = 0; '0' <= c && c <= '9'; c = getchar()) num = (num << 1) + (num << 3) + (c - '0');
    if (neg) num = -num;
    return num;
}

const int LIM = 1e6;
const int lim = pow(LIM / 9, 1.0/2);
int t, a, b;
bool p[lim + 1];
int pfs[LIM + 1];

void sieve() {
    for (int i = 3; i <= lim; i += 2) {
        if (!p[i]) {
            pfs[9 * i * i] = 1;
            for (int j = i * i; j <= lim; j += i) {
                p[j] = 1;
            }
        }
    }
}

void preprocess() {
    sieve();
    pfs[36] = pfs[6561] = 1;
    pfs[81] = 0;
    for (int i = 3; i <= LIM; ++i) {
        pfs[i] += pfs[i - 1];
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    preprocess();
    for (t = readInt(); t--; ) {
        a = readInt();
        b = readInt();
        cout << pfs[b] - pfs[a - 1] << '\n';
    }
}

#include <bits/stdc++.h>
using namespace std;
bool uc9(int n) {
    int d=2;
    for (int i=2; i<n; i++) if (n%i==0) d++;
    return d==9;
}
int dem(int a, int b) {
    int d=0;
    for (int i=a; i<=b; i++) if (uc9(i) && i%3==0) d++;
    return d;
}
int main() {
    int t;
    cin >> t;
    for (int i=0; i<t; i++) {
        int a,b;
        cin >> a >> b;
        cout << dem(a,b) << endl;
    }
}