#include<bits/stdc++.h>
using namespace std;
long long n,a,b,s[100010];
int main(){
	for(int i=2;i<=100000;i++){
		int t=1;
		for(int j=2;j<=sqrt(i);j++){
			if(i%j==0){
				t=0;
				break;	
			}
		}
		if(t==1){
			s[i]=s[i-1]+1;
		}else{
			s[i]=s[i-1];
		}
	}
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&a,&b);
		cout<<s[b]-s[a-1]<<endl;
	}
    return 0;
}