#include <fstream>
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
#define MAXNR 1000000

long long i,j,h,n,m;
long long a,b,nrdiv,auxb,sum,crt, nrzero, crt_sum,crt_poz;

int prim[1000005],nrprim;
long long divv[505];
bool neprim[1000005];

void generare()
{
    for(int i=3; i<=MAXNR; i+=2)
    {
        i=i;
        if(neprim[j]==false)
            for(int j=i+i; j<=MAXNR; j+=i)
                neprim[j]=true;
    }
    for(int i=2; i<=MAXNR; i++)
        if(!neprim[i])
             prim[++nrprim]=i;
}

int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    scanf("%d", &m);

    //generez toate numerele prime
    generare();

    for(i=1; i<=m; i++)
    {
        scanf("%lld%lld", &a,&b);

        nrdiv=0; auxb=b;

        //Formez toti factorii primi
        for(j=1; j<=nrprim; j++)
        {
            if(auxb==1 || prim[j] * prim[j] >b)
                break;

            if( auxb % prim[j] == 0 )
            {
                divv[++nrdiv] = prim [j];
                while(auxb % prim[j] == 0)
                    auxb /= prim[j];
            }
        }
        if(auxb!=1)
            divv[++nrdiv]=auxb;

        sum=0;

        //Parcurg toate combinatiile
        for(j=1; j <( 1<<nrdiv ); j++ )
        {
            crt=j; nrzero=0; crt_sum=1; crt_poz=0;

            for(h=0; h <=nrdiv; h++)
            {
                crt_poz++;
                if(j & (1<<h) && crt_poz <= nrdiv)
                {
                    nrzero++;
                    crt_sum= crt_sum * divv[crt_poz] ;
                }
            }

            if(nrzero % 2 == 1)
                sum+= ( a / crt_sum );
            else
                sum-= ( a / crt_sum );
        }
        printf("%lld\n",a-sum);
    }
}