#include <stdio.h>
#include <cmath>
long long div[100000],pos;
bool schimb[100000],ciur[300006];
long long a,b,temp,tx=0;
FILE *fin,*fout;
void ver()
{
    int ct=0;
    int mult=1;
    for(int i=1; i<pos; i++)
    {
        if(schimb[i]==1)
        {
            ct++;
            mult*=div[i];
        }
    }
    if(ct==0) return ;
    if(ct%2==0) tx-=a/mult;
    else if(ct%2!=0) tx+=a/mult;
}
void bcs(int pt)
{
    if(pt==pos) ver();
    else
    {
        for(int i=0; i<=1; i++)
        {
            schimb[pt]=i;
            bcs(pt+1);
        }
    }
}
int main()
{
    for(int i=2; i<=300005; i++)
    {
        if(ciur[i]==0)
        {
            for(int j=i; j<300005/i; j++)
            {
                ciur[i*j]=1;
            }
        }
    }
    fin=fopen("pinex.in","r");
    fout=fopen("pinex.out","w");
    int n;
    fscanf(fin,"%d",&n);
    for(int i=1; i<=n; i++)
    {
        pos=1;
        fscanf(fin,"%lld%lld",&a,&b);
        if(b==1)
        {
            fprintf(fout,"%lld\n",a);
        }
        else
        {

            long long siz=sqrt(b)+1;
            if(b%2==0)
            {
                div[pos]=2;
                pos++;
                while(b%2==0) b/=2;
            }
            for(long long j=3; j<=siz; j+=2)
            {
                if(ciur[j]==0)
                {
                    if(b%j==0)
                    {
                        div[pos]=j;
                        pos++;
                        while(b%j==0) b/=j;
                        if(b==1) break;
                    }
                }
            }
            if(b!=0)
            {
                div[pos]=b;
                pos++;
            }
            tx=0;
            for(int j=1; j<pos; j++) schimb[j]=0;
            bcs(1);
            fprintf(fout,"%lld\n",a-tx);
        }
    }
}