#include <bits/stdc++.h>
using namespace std;
int cnt = 1, k, a[10000000], ans[10000000], t, l, r;
bitset<100000010> vis;
int bitsum(int p){
	if(p < 10){
		return p;
	}
	return p % 10 + bitsum(p / 10);
}
bool isprime(int p){
	for(int i = 2; i * i < p; i++){
		if(p % i == 0){
			return false;
		}
	}
	return true;
}
void init(){
	int n = 100000000;
    for(int i = 2; i <= n; i++){
        if(!vis[i]){
            a[cnt] = i;
            cnt++;
        }
        for(int j = 1; j < cnt; j++){
            if(1ll * i * a[j] > n){
                break;
            }
            vis[i * a[j]] = true;
            if(i % a[j] == 0){
                break;
            }
        }
    }
    for(int i = 1; i <= cnt; i++){
    	if(isprime(bitsum(a[i]))){
    		ans[k] = a[i];
    		k++;
		}
	}
}
int main(){
	cin >> t;
	for(int i = 0; i < t; i++){
		cin >> l >> r;
		cout << (upper_bound(ans, ans + k, r) - ans) - (lower_bound(ans, ans + k, l) - ans) << endl;
	}
	return 0;
}

QAQ