#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;
}