#include <cstdio>
#include <algorithm>
using namespace std;
const int M = 100000; int Q, pn[M], pn2017[M];
int main() {
  for(int i = 2; i <= M; ++i) pn[i] = 1;
  for(int i = 2; i*i <= M; ++i) {
    if(!pn[i]) continue;
    for(int j = i*i; j <= M; j+=i) pn[j] = 0;
  }
  for(int i = 2; i <= M; ++i) {
    pn2017[i] = pn2017[i-1]+(pn[i]&&pn[(i+1)/2]);
  }
  scanf("%d", &Q);
  for(int i = 1, l, r; i <= Q; ++i) {
    scanf("%d %d", &l, &r);
    printf("%d\n", pn2017[r]-pn2017[l-1]);
  }
}