// Tổng độ dài của các truy vấn khôgn vượt quá 10^6
 
// tổng các (R(i) - L(i) + 1) không vượt quá 10^6
// => R(i) - L(i) + 1 không vượt quá 10^6
 
// nên tuy L(i), R(i) tối đa 10^9, nhưng độ dài đoạn lại đủ nhỏ.
// => Sàng trên đoạn 
 
// Ý tưởng thì vẫn là dựa vào sàng bình thường [2, N]
 
// Nhưng thay vì mình cứ mặc định for bội từ i * i, mình có thể for từ thằng bội đầu tiên của i mà >= L 
 
// bội đầu tiên của i mà >= L có công thức: ([L / i] làm tròn lên) * i
// (L / i) làm tròn lên = (L + i - 1) / i làm tròn xuống
// => ((L + i - 1) / i) * i
 
// => j = max(i * i, (L + i - 1) / i * i)
 
#include <bits/stdc++.h>
using namespace std; 
 
#define fst first
#define snd second 
 
typedef long long ll; 
typedef pair<int, int> ii; 
 
const ll LINF = (ll)1e18; 
const int INF = (int)1e9;
 
const int N = (int)1e6 + 5; 
 	// i: L -> R
 	// -> i - L  
 	// [0 -> R - L]   
 
bool isPrime[N]; 
 
int main() {
	ios::sync_with_stdio(0); 
	cin.tie(0); 
	int T; cin >> T; 
 
	// j = i * i   
	// j = ((L + i - 1) / i) * i 
	// => j = max(..., ...)
 
	while (T--) {
		int L, R; 
		cin >> L >> R; 
 
		L = max(L, 2); // trường hợp đặc biệt L = 1 sẽ dẫn đến sai lỗi đáng tiếc
					   // vì thường mình for từ 2 nên hay bị bỏ qua thèn 1 mà thèn 1 nó ko nguyên tố
					   // nên mặc định L >= 2 cho chắc cú
		for (int i = 0; i <= R - L; i++) isPrime[i] = true;  
 
		for (int i = 2; i * i <= R; i++) {
			for (int j = max(i * i, (L + i - 1) / i * i); j <= R; j += i) isPrime[j - L] = false; 
		}
 
		int cnt_prime = 0;   
		for (int i = 0; i <= R - L; i++) cnt_prime += (isPrime[i]); 
 
		cout << cnt_prime << '\n';
	}
}
 

Ly8gVOG7lW5nIMSR4buZIGTDoGkgY+G7p2EgY8OhYyB0cnV5IHbhuqVuIGtow7RnbiB2xrDhu6N0IHF1w6EgMTBeNgoKLy8gdOG7lW5nIGPDoWMgKFIoaSkgLSBMKGkpICsgMSkga2jDtG5nIHbGsOG7o3QgcXXDoSAxMF42Ci8vID0+IFIoaSkgLSBMKGkpICsgMSBraMO0bmcgdsaw4bujdCBxdcOhIDEwXjYKCi8vIG7Dqm4gdHV5IEwoaSksIFIoaSkgdOG7kWkgxJFhIDEwXjksIG5oxrBuZyDEkeG7mSBkw6BpIMSRb+G6oW4gbOG6oWkgxJHhu6cgbmjhu48uCi8vID0+IFPDoG5nIHRyw6puIMSRb+G6oW4gCgovLyDDnSB0xrDhu59uZyB0aMOsIHbhuqtuIGzDoCBk4buxYSB2w6BvIHPDoG5nIGLDrG5oIHRoxrDhu51uZyBbMiwgTl0KCi8vIE5oxrBuZyB0aGF5IHbDrCBtw6xuaCBj4bupIG3hurdjIMSR4buLbmggZm9yIGLhu5lpIHThu6sgaSAqIGksIG3DrG5oIGPDsyB0aOG7gyBmb3IgdOG7qyB0aOG6sW5nIGLhu5lpIMSR4bqndSB0acOqbiBj4bunYSBpIG3DoCA+PSBMIAoKLy8gYuG7mWkgxJHhuqd1IHRpw6puIGPhu6dhIGkgbcOgID49IEwgY8OzIGPDtG5nIHRo4bupYzogKFtMIC8gaV0gbMOgbSB0csOybiBsw6puKSAqIGkKLy8gKEwgLyBpKSBsw6BtIHRyw7JuIGzDqm4gPSAoTCArIGkgLSAxKSAvIGkgbMOgbSB0csOybiB4deG7kW5nCi8vID0+ICgoTCArIGkgLSAxKSAvIGkpICogaQoKLy8gPT4gaiA9IG1heChpICogaSwgKEwgKyBpIC0gMSkgLyBpICogaSkKCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOyAKCiNkZWZpbmUgZnN0IGZpcnN0CiNkZWZpbmUgc25kIHNlY29uZCAKCnR5cGVkZWYgbG9uZyBsb25nIGxsOyAKdHlwZWRlZiBwYWlyPGludCwgaW50PiBpaTsgCgpjb25zdCBsbCBMSU5GID0gKGxsKTFlMTg7IApjb25zdCBpbnQgSU5GID0gKGludCkxZTk7Cgpjb25zdCBpbnQgTiA9IChpbnQpMWU2ICsgNTsgCiAJLy8gaTogTCAtPiBSCiAJLy8gLT4gaSAtIEwgIAogCS8vIFswIC0+IFIgLSBMXSAgIAoKYm9vbCBpc1ByaW1lW05dOyAKCmludCBtYWluKCkgewoJaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7IAoJY2luLnRpZSgwKTsgCglpbnQgVDsgY2luID4+IFQ7IAoKCS8vIGogPSBpICogaSAgIAoJLy8gaiA9ICgoTCArIGkgLSAxKSAvIGkpICogaSAKCS8vID0+IGogPSBtYXgoLi4uLCAuLi4pCgoJd2hpbGUgKFQtLSkgewoJCWludCBMLCBSOyAKCQljaW4gPj4gTCA+PiBSOyAKCQoJCUwgPSBtYXgoTCwgMik7IC8vIHRyxrDhu51uZyBo4bujcCDEkeG6t2MgYmnhu4d0IEwgPSAxIHPhur0gZOG6q24gxJHhur9uIHNhaSBs4buXaSDEkcOhbmcgdGnhur9jCgkJCQkJICAgLy8gdsOsIHRoxrDhu51uZyBtw6xuaCBmb3IgdOG7qyAyIG7Dqm4gaGF5IGLhu4sgYuG7jyBxdWEgdGjDqG4gMSBtw6AgdGjDqG4gMSBuw7Mga28gbmd1ecOqbiB04buRCgkJCQkJICAgLy8gbsOqbiBt4bq3YyDEkeG7i25oIEwgPj0gMiBjaG8gY2jhuq9jIGPDugoJCWZvciAoaW50IGkgPSAwOyBpIDw9IFIgLSBMOyBpKyspIGlzUHJpbWVbaV0gPSB0cnVlOyAgCgoJCWZvciAoaW50IGkgPSAyOyBpICogaSA8PSBSOyBpKyspIHsKCQkJZm9yIChpbnQgaiA9IG1heChpICogaSwgKEwgKyBpIC0gMSkgLyBpICogaSk7IGogPD0gUjsgaiArPSBpKSBpc1ByaW1lW2ogLSBMXSA9IGZhbHNlOyAKCQl9CgoJCWludCBjbnRfcHJpbWUgPSAwOyAgIAoJCWZvciAoaW50IGkgPSAwOyBpIDw9IFIgLSBMOyBpKyspIGNudF9wcmltZSArPSAoaXNQcmltZVtpXSk7IAoKCQljb3V0IDw8IGNudF9wcmltZSA8PCAnXG4nOwoJfQp9Cg==