#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb(x) push_back(x)
#define N 100005
#define MOD 1000000007
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
#define LSOne(S) (S & (-S))
// Cribe
bitset<N> bs;
vector<int> primes;
void sieve()
{
int n = N;
bs.set();
bs[0] = bs[1] = 0;
for(ll i = 2; i <= n; i++)
if(bs[i])
{
for(ll j = i * i; j <= n; j += i)
bs[j] = 0;
primes.push_back(i);
}
}
// BIT (Fenwick Tree) methods
vi t;
void inc(int i, int val)
{
for(i++; i <= N; i += LSOne(i))
t[i] += val;
}
int rsq(int i)
{
int sum = 0;
for(i++; i; i -= LSOne(i))
sum += t[i];
return sum;
}
int rsq(int l, int r)
{
return rsq(r) - rsq(l - 1);
}
int main() {
fastIO;
int q, n, k;
cin >> q;
// Obtain the prime numbers up to 100000
sieve();
// Initialize the BIT (Fenwick Tree)
t = vi(N + 1, 0);
for(int i = 0; i < N; i++)
inc(i, 1);
// Create the array of queries for working with them in offline mode
vector<pair<pair<int, int>, int>> queries;
for(int i = 0; i < q; i++)
{
cin >> n >> k;
queries.pb(make_pair(make_pair(k, n), i));
}
// Sort the queries by decreasing K
sort(queries.rbegin(), queries.rend());
int primeIndex = primes.size() - 1;
vector<int> ans(q);
for(int i = 0; i < q; i++)
{
k = queries[i].first.first;
n = queries[i].first.second;
// Update (remove) all the elements with prime divisors greater than current query's K
while(primeIndex >= 0 && primes[primeIndex] > k)
{
for(int j = primes[primeIndex]; j < N; j += primes[primeIndex])
{
if(rsq(j, j) != 0)
inc(j, -1);
}
primeIndex--;
}
// Set the answer for the query
ans[queries[i].second] = rsq(2, n);
}
for(int i = 0; i < q; i++)
{
cout << ans[i] << "\n";
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBmYXN0SU8gaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7IGNpbi50aWUoMCk7IGNvdXQudGllKDApOwojZGVmaW5lIHBiKHgpIHB1c2hfYmFjayh4KSAKI2RlZmluZSBOIDEwMDAwNSAKI2RlZmluZSBNT0QgMTAwMDAwMDAwNwp0eXBlZGVmIHZlY3RvcjxpbnQ+IHZpOwp0eXBlZGVmIHZlY3Rvcjx2aT4gdnZpOwp0eXBlZGVmIHBhaXI8aW50LCBpbnQ+IHBpaTsKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgdW5zaWduZWQgbG9uZyBsb25nIHVsbDsKCiNkZWZpbmUgTFNPbmUoUykgKFMgJiAoLVMpKQoKLy8gQ3JpYmUKYml0c2V0PE4+IGJzOyAKdmVjdG9yPGludD4gcHJpbWVzOwp2b2lkIHNpZXZlKCkgCnsKCWludCBuID0gTjsKCWJzLnNldCgpOyAKCWJzWzBdID0gYnNbMV0gPSAwOyAKCWZvcihsbCBpID0gMjsgaSA8PSBuOyBpKyspIAoJCWlmKGJzW2ldKQoJCXsKCQkJZm9yKGxsIGogPSBpICogaTsgaiA8PSBuOyBqICs9IGkpCgkJCQlic1tqXSA9IDA7CgkJCXByaW1lcy5wdXNoX2JhY2soaSk7IAoJCX0KfQoKLy8gQklUIChGZW53aWNrIFRyZWUpIG1ldGhvZHMKdmkgdDsgCnZvaWQgaW5jKGludCBpLCBpbnQgdmFsKQp7Cglmb3IoaSsrOyBpIDw9IE47IGkgKz0gTFNPbmUoaSkpCgkJdFtpXSArPSB2YWw7Cn0KaW50IHJzcShpbnQgaSkKewoJaW50IHN1bSA9IDA7Cglmb3IoaSsrOyBpOyBpIC09IExTT25lKGkpKQoJCXN1bSArPSB0W2ldOwoJcmV0dXJuIHN1bTsKfQppbnQgcnNxKGludCBsLCBpbnQgcikKewoJcmV0dXJuIHJzcShyKSAtIHJzcShsIC0gMSk7Cn0KCmludCBtYWluKCkgewoJZmFzdElPOwoJaW50IHEsIG4sIGs7CgljaW4gPj4gcTsKCS8vIE9idGFpbiB0aGUgcHJpbWUgbnVtYmVycyB1cCB0byAxMDAwMDAKCXNpZXZlKCk7CgkvLyBJbml0aWFsaXplIHRoZSBCSVQgKEZlbndpY2sgVHJlZSkKCXQgPSB2aShOICsgMSwgMCk7Cglmb3IoaW50IGkgPSAwOyBpIDwgTjsgaSsrKQoJCWluYyhpLCAxKTsKCS8vIENyZWF0ZSB0aGUgYXJyYXkgb2YgcXVlcmllcyBmb3Igd29ya2luZyB3aXRoIHRoZW0gaW4gb2ZmbGluZSBtb2RlCgl2ZWN0b3I8cGFpcjxwYWlyPGludCwgaW50PiwgaW50Pj4gcXVlcmllczsKCWZvcihpbnQgaSA9IDA7IGkgPCBxOyBpKyspCgl7CgkJY2luID4+IG4gPj4gazsKCQlxdWVyaWVzLnBiKG1ha2VfcGFpcihtYWtlX3BhaXIoaywgbiksIGkpKTsKCX0KCS8vIFNvcnQgdGhlIHF1ZXJpZXMgYnkgZGVjcmVhc2luZyBLCglzb3J0KHF1ZXJpZXMucmJlZ2luKCksIHF1ZXJpZXMucmVuZCgpKTsKCWludCBwcmltZUluZGV4ID0gcHJpbWVzLnNpemUoKSAtIDE7Cgl2ZWN0b3I8aW50PiBhbnMocSk7Cglmb3IoaW50IGkgPSAwOyBpIDwgcTsgaSsrKSAKCXsKCQlrID0gcXVlcmllc1tpXS5maXJzdC5maXJzdDsKCQluID0gcXVlcmllc1tpXS5maXJzdC5zZWNvbmQ7CgkJLy8gVXBkYXRlIChyZW1vdmUpIGFsbCB0aGUgZWxlbWVudHMgd2l0aCBwcmltZSBkaXZpc29ycyBncmVhdGVyIHRoYW4gY3VycmVudCBxdWVyeSdzIEsKCQl3aGlsZShwcmltZUluZGV4ID49IDAgJiYgcHJpbWVzW3ByaW1lSW5kZXhdID4gaykKCQl7CgkJCWZvcihpbnQgaiA9IHByaW1lc1twcmltZUluZGV4XTsgaiA8IE47IGogKz0gcHJpbWVzW3ByaW1lSW5kZXhdKQoJCQl7CgkJCQlpZihyc3EoaiwgaikgIT0gMCkKCQkJCQlpbmMoaiwgLTEpOwoJCQl9CgkJCXByaW1lSW5kZXgtLTsKCQl9CgkJLy8gU2V0IHRoZSBhbnN3ZXIgZm9yIHRoZSBxdWVyeQoJCWFuc1txdWVyaWVzW2ldLnNlY29uZF0gPSByc3EoMiwgbik7Cgl9Cglmb3IoaW50IGkgPSAwOyBpIDwgcTsgaSsrKQoJewoJCWNvdXQgPDwgYW5zW2ldIDw8ICJcbiI7Cgl9CglyZXR1cm4gMDsKfQ==