#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#define inputt int t;cin>>t;
#define pi acos(-1.0)
#define lson o*2,l,m
#define rson o*2+1,m+1,r
#define INF 0x7f7f7f7f
#define lowbit(X) ((X)&(-X))
#define clr(X,Y) memset(X,Y,sizeof(X))
typedef long long ll;
using namespace std;
int hs[101000];
ll pri[101000];
int cnt=0;
void init(){
    for(int i=2;i<101000;i++){
        int k=2;
        if(hs[i]==0)pri[cnt++]=i;
        while(i*k<101000){
            hs[i*k]=1;
            k++;
        }
    }
}
int main(){
    init();
    //for(int i=0;i<cnt;i++)printf("%d ",pri[i]);
    inputt
    while(t--){
        ll n,m;
        int ans=0;
        scanf("%I64d%I64d",&n,&m);
        if(n<=m){
            printf("0\n");
            continue;
        }
        for(int i=0;i<cnt;i++){
            if(m%pri[i]!=0&&pri[i]*m<n)ans++;
            else if(m%pri[i]==0&&pri[i]*m<n){
                ans++;
                break;
                }
            else break;
        }
        printf("%d\n",ans);
    } 
    return 0;
}