#include <stdio.h>
#include <cmath>
long long div[100000],pos;
int fprim[80000];
bool schimb[100000],ciur[300006];
long long a,b,temp,tx=0;
FILE *fin,*fout;
void ver()
{
    int ct=0;
    long long 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()
{
    int tt=0;
    for(int i=2; i<=300005; i++)
    {
        if(ciur[i]==0)
        {
            fprim[++tt]=i;
            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
        {
            for(int j=1;j<=tt;j++)
            {
                if(b%fprim[j]==0)
                {
                    div[pos]=fprim[j];
                    ++pos;
                    while(b%fprim[j]==0) b/=fprim[j];
                }
            }
            if(b!=1)
            {
                div[pos]=b;
                pos++;
            }
            tx=0;
            for(int j=1; j<pos; j++) schimb[j]=0;
            bcs(1);
            fprintf(fout,"%lld\n",a-tx);
        }
    }
}