#include <fstream>
using namespace std;

ifstream cin("pinex.in");
ofstream cout("pinex.out");

long long a,b,m,fact[20],k,rez,i,n,nr,nr1;
int prime[100000],v[20];
bool c[1000005];

void ciurr();
void solve(long long a, long long b);
void submultimi();
int main()
{
    ciurr();
    cin>>n;
    for(i=1; i<=n; ++i)
    {
        cin>>a>>b;
        solve(a,b);
    }
    return 0;
}
void ciurr()
{
    c[0]=c[1]=1;
    for(int i=2; i*i<=1000000; i++)
        if(c[i]==0)
        {
            for(int j=i*i; j<=1000000; j=j+i)
                c[j]=1;
        }

    for(i=2; i<=1000000; i++)
        if(c[i]==0) prime[++k]=i;
}


void solve(long long a, long long b)
{
    ///k
    rez=0;
    int ind=1;
    nr=0;

    while(b>1 && prime[ind]*prime[ind]<=b)
    {
        if(b%prime[ind]==0)
        {
            while(b%prime[ind]==0) b=b/prime[ind];
            fact[++nr]=prime[ind];
        }

        ind++;

    }
    if(b>1) fact[++nr]=b;

    long long i=0;

    long long  p=1;


        for(i=1;i<(1<<nr);++i)
        {
                p=1;
                nr1=0;
               long long  aux=i;
               int idx=1;

               while(aux>0)
               {
                   if(aux%2==1)
                   {
                    p*=(fact[idx]);
                   nr1++;
                   }

                ++idx;
                aux/=2;

               }

        if(nr1%2==0) rez-=a/p;
        else rez+=a/p;

        }

    cout<<a-rez<<"\n";

}