#include<stdio.h>
#define lim 100007 

bool b[lim+1];
int p[lim],n,d,T,tot;

int main()
{
    for (int i=2;i<=lim;i++) if (!b[i]) for (int j=i<<1;j<=lim;j+=i) b[j]=1;
    for (int i=2;i<=lim;i++) if (!b[i]) p[tot++]=i;
    p[tot]=1000000000;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&d);
        int i;
        for (i=0;i<tot && d*p[i]<n;i++) if (d % p[i]==0) 
        {
            i++;
            break;
        }
        printf("%d\n",i);
    }
}