#include<bits/stdc++.h>
#define int long long
#define DIM 100001
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
unordered_map <int, bool> mp;
bitset <DIM> prime;
vector <int> primes;
int query, a, b, i, j;
int solve(){
    mp.clear();
    for(i=0;i<primes.size();i++){
        if(primes[i] > b)
        break;
        if(b % primes[i] == 0){
            j = primes[i];
            while(j <= a){
                mp[j] = 1;
                j += primes[i];
            }
        }
    }
    return a - mp.size();
}
void Eratostene(){
    for(i=2;i<DIM;i++)
        if(!prime[i]){
            primes.push_back(i);
            for(j=2;j*i<DIM;j++)
                prime[i * j] = 1;
        }
}
signed main(){
    Eratostene();
    fin >> query;
    while(query--){
        fin >> a >> b;
        fout << solve() << "\n";
    }
}