#include <fstream>
#include <iostream>
#define int long long
using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

int q,k,k2;
long long fp[50005],r,p[1000005],dprim[1000005],a,b;

void ciur()
{
    k2=0;

    for(int i=2;i<=1000000;i++)
        p[i]=1;
    for(int i=2;i<=1000000;i++)
        if(p[i])
        {
            dprim[++k2]=i;
            for(int j=i+i;j<=1000000;j+=i)
                p[j]=0;
        }
}

int factprimi(int b)
{
    int x=0;
    int i=1;
    while(b!=1)
    {
        if(b%dprim[i]==0)
        {
            fp[++x]=dprim[i];
            while(b%dprim[i]==0)
                b/=dprim[i];
        }
        i++;
        if(dprim[i]*dprim[i]>b && b>1)
        {
            fp[++x]=b;
            //fout<<"fprim"<<fp[x]<<endl;
            b=1;
        }
    }
    return x;
}

int pinex(int a)
{
    int r=a;
    //fout<<r<<endl;
    int lim=(1<<k)-1;
    for(int i=1;i<=lim;i++)
    {
        int p=1;
        int cnt=0;
        for(int j=0;(1<<j)<=i;j++)
            if((i&(1<<j))!=0)
            {
                cnt++;
                p=p*fp[j+1];
                //fout<<"fprim"<<fp[j+1]<<endl;
            }
        if(cnt%2==1)
            r=r-a/p;
        else
            r=r+a/p;
        //fout<<r<<" "<<a<<" "<<p<<endl;
    }
    return r;
}

signed main()
{
    fin>>q;
    ciur();
    while(q--)
    {
        //long long a;
        fin>>a>>b;
        //fout<<a<<" "<<b<<endl<<q<<endl;
        k=factprimi(b);
        fout<<pinex(a)<<endl;
    }
    return 0;
}