#include <iostream>
#include <cmath>
using namespace std;
 
bool is_prime(int m){
	if (m < 2) return false;
	if (m < 4) return true;
	if (m % 2 == 0 || m % 3 == 0) return false;
	int limit = sqrt(m);
	for (int i = 5; i <= limit; i += 6){
		if (m % i == 0) return false;
		if (m % (i+2) == 0) return false;
	}
	return true;
}
 
int prime_count(int k, int l){
	int p_c = 0;
	for (int i = k; i < l + 1; i++){
		if(is_prime(i))p_c++;
	}
	return p_c;
}
 
int main() {
	int n;
	cin >> n;
	int t [2*n];
	for (int i = 0; i < n * 2; i++){
		cin >> t[i];
	}
	for (int k = 0; k < n; k++){
		cout << prime_count(t[2*k],t[2*k+1]) << "\n";
	}
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y21hdGg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpib29sIGlzX3ByaW1lKGludCBtKXsKCWlmIChtIDwgMikgcmV0dXJuIGZhbHNlOwoJaWYgKG0gPCA0KSByZXR1cm4gdHJ1ZTsKCWlmIChtICUgMiA9PSAwIHx8IG0gJSAzID09IDApIHJldHVybiBmYWxzZTsKCWludCBsaW1pdCA9IHNxcnQobSk7Cglmb3IgKGludCBpID0gNTsgaSA8PSBsaW1pdDsgaSArPSA2KXsKCQlpZiAobSAlIGkgPT0gMCkgcmV0dXJuIGZhbHNlOwoJCWlmIChtICUgKGkrMikgPT0gMCkgcmV0dXJuIGZhbHNlOwoJfQoJcmV0dXJuIHRydWU7Cn0KCQppbnQgcHJpbWVfY291bnQoaW50IGssIGludCBsKXsKCWludCBwX2MgPSAwOwoJZm9yIChpbnQgaSA9IGs7IGkgPCBsICsgMTsgaSsrKXsKCQlpZihpc19wcmltZShpKSlwX2MrKzsKCX0KCXJldHVybiBwX2M7Cn0KCmludCBtYWluKCkgewoJaW50IG47CgljaW4gPj4gbjsKCWludCB0IFsyKm5dOwoJZm9yIChpbnQgaSA9IDA7IGkgPCBuICogMjsgaSsrKXsKCQljaW4gPj4gdFtpXTsKCX0KCWZvciAoaW50IGsgPSAwOyBrIDwgbjsgaysrKXsKCQljb3V0IDw8IHByaW1lX2NvdW50KHRbMiprXSx0WzIqaysxXSkgPDwgIlxuIjsKCX0KCXJldHVybiAwOwp9

MgoxIDcKMyA2

2
1 7
3 6