#include <iostream>
#include <string.h>
using namespace std;

int input[20002][2];
bool primes[1000002];

void dyz()
{
	// Magiczne linijki
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, big = 0;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> input[i][0] >> input[i][1];
		if (input[i][1] > big)
		{
			big = input[i][1];
		}
	}
	big++;

	// Sito
	memset(primes, true, big + 2);
	primes[0] = false;
	primes[1] = false;

	for (int i = 2; i * i <= big; i++)
	{
		if (primes[i])
		{
			for (int j = i * i; j < big; j += i)
			{
				primes[j] = false;
			}
		}
	}

	// Liczenie
	for (int i = 0; i < n; i++)
	{
		int start = input[i][0];
		int end = input[i][1];
		int counter = 0;
		for (int j = start; j <= end; j++)
		{
			if (primes[j])
			{
				counter++;
			}
		}
		cout << counter << "\n";
	}
}