#include <fstream>
#define NMAX 1000002
using namespace std;
ifstream  fin("pinex.in");
ofstream fout("pinex.out");
int M;
long long A,B,ans,nrfct,fct[30],x[30],nr,prod;

void BACK(int k)
{
    for(int i=x[k-1]+1; i<=nrfct; i++)
    {
        x[k]=i;

        prod=prod*fct[x[k]];
        nr++;

        if(nr%2==1)
        {
            ans=ans-A/prod;
        }
        else
        {
            ans=ans+A/prod;
        }

        BACK(k+1);
    }

    nr--;
    prod=prod/fct[x[k-1]];
    x[k]=0;
}

void rezolvare()
{
    int d;

    fct[0]=1;
    nrfct=0;
    d=2;
    while(B>1)
    {
        if(B%d==0)
        {
            fct[++nrfct]=d;
            while(B%d==0)
            {
                B=B/d;
            }
        }

        d++;
        if(B>1 && d*d>B)
        {
            d=B;
        }
    }

    ans=A;
    nr=0;
    prod=1;
    BACK(1);

    fout<< ans << "\n";
}

int main()
{
    fin>>M;

    for(int q=1; q<=M; q++)
    {
        fin>>A>>B;

        rezolvare();
    }

    return 0;
}