#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define endl '\n'
#define EPS 1e-9
using namespace std;
void Haidy();

const ll MOD = (int)1e9 + 7;
const auto PI = std::acos(-1);

int knightX[] = {-2, -2, 2, 2, 1, 1 , -1, -1};
int knighty[] = {-1, 1, -1, 1, -2, 2, -2, 2};

int dx[] = {1, 0, -1, 0, -1, -1, 1, 1};
int dy[] = {0, -1, 0, 1, -1, 1, -1, 1};
char di[] = {'D', 'L', 'U', 'R'};


int l , r;
vector<int> spf[55], primes;
bool isPrime(int n){
    if(n == 1) return 0;
    for(int i = 2; i < n; i++){
        if(n%i == 0)
            return 0;
    }
    return 1;
}
void pre(){
    for(int i = 2; i<=50; i++){
        if(isPrime(i))
            primes.push_back(i);
        for(auto p: primes){
            if(i %p == 0){
                spf[i].push_back(p);
            }
        }
    }
}

int target;
vector < vector < ll > > dp;

ll rec(int cur_sum , int msk){
    if(cur_sum >= target){
        return cur_sum == target;
    }

    ll ret = 0;
    for(int i = 1; i <= 50; i++){
        bool ok = 1;
        for(auto& p : spf[i]){
            for(int k = 0 ; k < primes.size() ; k++){
                // only one pit 1
                if(p == primes[k]) if(msk & (1 << k)) ok = 0;
            }

        }
        if(ok){
            for(auto& p : spf[i]){
                for(int k = 0 ; k < primes.size() ; k++){
                    // only one pit 1
                    if(p == primes[k]) msk |= (1 << k);
                }

            }
            ret += rec(cur_sum+i, msk);

            for(auto& p : spf[i]){
                for(int k = 0 ; k < primes.size() ; k++){
                    // only one pit 1
                    if(p == primes[k]) msk &= !(1 << k);

                }

            }

        }
    }
    return ret;
}


void solveTest() {
    cin >> l >> r;
    ll ans = 0;
    for(int i =l ; i <= r; i++){
        target =i;
        ans += rec(0, set<int>());
    }
    cout << ans << endl;
}

int main() {
    Haidy();
    pre();
    int testCases = 1;
    cin >> testCases;
    cout << fixed << setprecision(9);
    while(testCases--) {
        solveTest();
    }
    return 0;
}

void Haidy() {
    cin.tie(nullptr), cout.tie(nullptr), cin.sync_with_stdio(false), cout.sync_with_stdio(false);
#ifdef Clion
    freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif
}