#include <bits/stdc++.h>
#define dim 1000004
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
bitset <dim> fr;
long long prim[dim/10];
long long k,q,i,n,st,nr,v[200],sum;
unsigned long long a,b,p=1;
void backtr(int pas,int nr1)
{
    if(pas>nr)
    {
        if(p==1)
            return;
        if(nr1%2==1)
        {
            sum+= a/p;
        }
        else
        {
            sum-=a/p;
        }
        return;
    }
    p*=v[pas];
    backtr(pas+1,nr1+1); /// am inmultit cu elementul din v de  pe pozitia pas
    p/=v[pas];
    backtr(pas+1,nr1);
}
void  ciur()
{
    fr[1]=fr[0]=1;
    for(int i=4; i<=dim; i+=2)
        fr[i]=1;
    prim[++k]=2;
    for(int i=3; i<=dim; i+=2)
    {
        if(fr[i]==0)
        {
            prim[++k]=i;
            for(int j=2*i; j<=dim; j+=i)
                fr[j]=1;
        }
    }
   // cout<<k;
}
int main()
{
    ciur();
    fin>>q;
    for(; q; q--)
    {
        fin>>a>>b;
        /// descompun a
        st=1;
        nr=0;
        //   cout<<prim[1];
        while(prim[st]*prim[st]<=b&&st<=k)
        {
            if(b%prim[st]==0)
            {
                v[++nr]=prim[st];
                while(b%prim[st]==0)
                    b/=prim[st];
            }
            st++;
        }
        if(b>1)
        {
            v[++nr]=b;
        }
        sum=0;
        if(nr==0){
            sum=a;
        }else
        backtr(1,0);
        fout<<a-sum<<"\n";
    }
}