#include <iostream>    
#include <stdio.h>    
#include <cmath>    
#include <algorithm>    
#include <string>  
#include <string.h>       
#include <vector>    
#include <queue>    
#include <stack>
#include <map>

using namespace std;

#define ll long long

const int N = 200000;     
int prime[N] = {0},num_prime = 0;      
int isNotPrime[N] = {1, 1};   

int mnfac(int x,int limit1){
    for(int i=0;i<num_prime;i++){
        if(prime[i] * prime[i]> x){
            break;
        }
        if(prime[i] >= limit1){
            return limit1;
        }
        if(x % prime[i] == 0){
            return prime[i];
        }
    }
    return x;
}

int main(){
    
    for(long i = 2 ; i < N ; i ++)         
        {              
        if(! isNotPrime[i])                 
            prime[num_prime ++]=i;    
        //关键处1          
        for(long j = 0 ; j < num_prime && i * prime[j] <  N ; j ++)  
            {                 
                isNotPrime[i * prime[j]] = 1;    
            if( !(i % prime[j] ) )  //关键处2                    
                break;             
        }          
    }  
    
    /*for(int i=0;i<=10;i++){
        cout<<prime[i]<<endl;
    }
    cout<<prime[num_prime-1]<<endl;
    cout<<num_prime<<endl;
    */
    
    int t;
    cin>>t;
    while(t--){
        int n,d;
        //cin>>n>>d;
        scanf("%d%d",&n,&d);
        int limit1 = (n-1)/d;
        int limit2 = mnfac(d,limit1);
        int limit = min(limit1,limit2);
        
        int ans = upper_bound(prime,prime+17900,limit)-prime;
        printf("%d\n",ans);
    }
}