#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<cctype>
#include<queue>
#include<vector>
#include<string>
#include<map>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=100005;
const LL mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1);
int pri[40000];
bool v[40000];
void Init()
{
    int k=0;
    for(int i=2;i<40000;i++)
        if(!v[i])
    {
        pri[k++]=i;
        for(int j=i+i;j<40000;j+=i)
            v[j]=true;
    }
}
LL maPri,maSum,ans;
int main()
{
//    freopen("test1.in","r",stdin);
//    freopen("test2.out","w",stdout);
    Init();
    int T;
    LL n,d;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%I64d%I64d",&n,&d);
        n--;
        maPri=n/d;
        if(maPri>d)
            maPri=d;
        ans=0;
        for(int i=0;pri[i]<=maPri;i++)
        {
            ans++;
            if(d%pri[i]==0)
                break;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}