#include<bits/stdc++.h>
#define ll long long
using namespace std;

int check(int n){
    int s=0;
    while (n>0){
        s+=n%10;
        n/=10;
    }
    return s;
}
void sangnt(ll l,ll r){
	int x[r-l+1];
	int s=0;
	for(ll i=l;i<=r;i++){
		x[i-l] = 1;
	}
	for(ll i=2;i<=sqrt(r);i++){
		for(ll j=max(i*i,(l+i-1)/i*i);j<=r;j+=i){
			x[j-l] =0;
		}
	}
	for(ll i=max(2ll,l);i<= r;i++){
		if(x[i-l] && check(i)%5==0){
            s+=1;
		}
	}cout<<s;
}

int main(){
    ll T,s=0,l,r;
    cin>>T;
    for (int i=0;i<T;i++){
        cin>>l>>r;
        sangnt(l,r);
    }
    //meothinhle
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int t, l, r, ma[1000005], dem;
bool kt5(int n)
{
    int to = 0;
    while(n > 0)
    {
        to += n % 10;
        n /= 10;
    }
    return to % 5 == 0;
}
void sang()
{
    for(int a = 2; a <= 1000000; a++)
        ma[a] = 1;

    for(int a = 2; a * a <= 1000000; a++)
    {
        if(ma[a])
        {
            for(int b = a * a; b <= 1000000; b += a)
                ma[b] = 0;

            if(!kt5(a))
                ma[a] = 0;
        }
    }
}
int main()
{
    sang();
    cin >> t;
    while(t--)
    {
        cin >> l >> r;
        for(int i = l; i <= r; i++)
            if(ma[i]) dem++;
        cout << dem << "\n";
    }
    return 0;
}