#include<iostream>
#include<vector>
using namespace std;
const int N=1e7+5;
vector<int> v;//v质数列表
bool b[N];//判断质数 0为质数 1为合数
bool zb[N];//判断双重质数
void zs(){
  for(int i=2;i<=N;i++){
    if(!b[i]){
      v.push_back(i);
    }
    for(int j=0;j<v.size();j++){
      int t=v[j]*i;
      if(t>N) break;
      b[t]=1;
      if(i%v[j]==0) break;
    }
  }

}

void sczh(){
  for(int i=0;i<v.size();i++){
    int t=v[i];
    int sum=0;
    while(t!=0){
      sum+=t%10;
      t/=10;
    }
    if(!b[sum]) zb[v[i]]=1;
  }
}

int main(){
  int m;
  cin>>m;
  zs();
  sczh();
  for(int i=1;i<=m;i++){
    int a,b,ans=0;
    cin>>a>>b;
    for(int j=a;j<=b;j++){
      if(zb[j]) ans++;
    }
    cout<<ans<<endl;
  }
   
  return 0;
}