#include<fstream>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int div1[10001],i,a,b,n,k,j,sol,t,nrd;
void descp(int nr)
{
    int d=2;
    while(d*d<=nr)
   {
       while(nr%d==0)
       {
           div1[++k]=d;
           nr=nr/d;
       }
       if(d==2)
       d++;
       else
    d=d+2;
   }
   if(nr>1)
    div1[++k]=nr;
}
int main ()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>a>>b;
        k=0;
        descp(b);
        nrd=0;
       for(j=2;j<=a;j++)
       {
           for(t=1;t<=k;t++)
           {
               if(j%div1[t]==0)
               {
                   nrd++;
                   break;
               }
           }
       }
       g<<a-nrd<<'\n';
    }
    return 0;
}