#include <fstream>
#include <bitset>
#include <cmath>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int v[100001],i,j,l,m,o,con,z,u;
bitset <1000001> prim;
long long ve[25],c,nr1,nr,a,b;
int main()
{
    v[1]=2,l=1;
    for (i=3;i<=1000000;i+=2)
    if (prim[i]==false)
    {
        j=i*i;
        if (j/i==i)
            for (j=i*i;j<=1000000;j+=i)
                 prim[j]=true;
        v[++l]=i;
    }
    f>>m;
    for (i=1;i<=m;i++)
    {
         f>>a>>b;
         c=sqrt(b);
         o=0;
         for (j=1;j<=l && v[j]<=c;j++)
            if (b%v[j]==0)
         {
             ve[++o]=v[j];
             while(b%v[j]==0)
                b=b/v[j];
         }
        if (b>1)
            ve[++o]=b;
         con=1<<o;
         nr1=0;
         for (z=1;z<con;z++)
         {
             nr=a;
             u=0;
             for (j=1;j<=o;j++)
             if (z &(1<<(j-1)))
             u++,nr=nr/ve[j];
             if (u%2==0)
                nr1-=nr;
             else nr1+=nr;
         }
         g<<a-nr1<<'\n';


    }
    return 0;
}