Tap 2014-I

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define dprint(v) cout << #v"=" << v << endl
#define forr(i, a, b) for(int i=(a); i<(b); i++)
#define forn(i, n) forr(i, 0, n)
#define dforn(i, n) for(int i=(n)-1; i>=0; i--)
#define forall(it,v) for(typeof((v).begin()) it=(v).begin();it!=(v).end();++it)
#define sz(c) ((int)c.size())
#define zero(v) memset(v, 0, sizeof(v))
typedef long long ll;
#define ii pair<int, int>
#define mkp make_pair
#define fst first
#define snd second
#define pb push_back
#define TCRIB 10000000
#define MAXP 3162	//no necesariamente primo
#define T 100

int p1[10000],p2[10000];
int criba[TCRIB];
vector<int> primos;

void buscarprimos(){
	forr(p, 2, MAXP+1) if(!criba[p]){
		primos.push_back(p);
		for(int m=2*p; m<=TCRIB; m+=p)//borro los multiplos de p
			if(!criba[m])criba[m]=p;
	}
}

int m, M; 

int main()
{
#ifndef ONLINE_JUDGE
	//~ freopen("i.in", "r", stdin);
#endif
	
	buscarprimos();

   forn (i, TCRIB)
		if (!criba[i])
			criba[i] = i;
	
	int cant = 0;
	forr (i,2,TCRIB){
		M = i+1;
		forr (j, i, min (i+T,TCRIB)){
			if (j-criba[j] < i)
				M = max (j+criba[j], M);
			if (j >= M){
				p1[cant] = i; p2[cant++] = j;}
			if (M >= i+T)
				break;			
		}
		
	}
	int a, b,rta,t;
	cin >> t;
	while (t--){
		cin >> a >> b;
		rta = 0;
		forn (i, cant)
			if (p1[i] >= a && p2[i] <= b)
				rta++;
		cout << rta << endl;
	}
	
	
    return 0;
}