/**
#include <fstream>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int v[1000001],prime[80000],diviz[300],g[300];
int i,j,k,n,d,nr;
long long a,b,aux,total;
int main()
{
    for(i=2; i<1000000; i++)
        if(v[i]==0)
        {
            for(j=i+i; j<1000000; j+=i)
                v[j]=1;
            prime[++k]=i;
        }
    fin>>n;
    for(; n--;)
    {
        fin>>a>>b;
        i=total=0;
        for(d=1; d<=k && b!=1 && prime[d]<=b/prime[d]; d++)
            if(b%prime[d]==0)
            {
                diviz[++i]=prime[d];
                while(b%prime[d]==0)
                    b/=prime[d];
            }
        if(b>1)
            diviz[++i]=b;

        ///for(j=0; j<20; j++)
        ///    g[j]=0;
        g[0] = 0;
        while(!g[0])
        {
            j=i;
            while(g[j])
            {
                g[j]=0;
                j--;
            }
            if(j<1)
                break;

            g[j]=1;
            aux=1;
            nr=0;
            for(; j; j--)
                if(g[j])
                {
                    nr++;
                    aux*=diviz[j];
                }
            if(nr&1)
                total+=a/aux;
            else
                total-=a/aux;
        }
        fout<<a-total<<"\n";
    }
}
**/
#include <fstream>
#include <cstring>
#include <bitset>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");

bitset<1000001> B;

int w[100];
long long P[300000];
long long x[100];

long long a, b, e, nr, y, sol, k, i, j, p, m;

int main() {
    for (i=2;i<=1000000;i++)
        if (!B[i]) {
            P[++p] = i;
            for (j=i+i;j<=1000000;j+=i)
                B[j] = 1;
        }
    fin>>m;
    for (;m--;) {
        fin>>a>>b;
        e = b;
        k = 0;
        for (i=1;P[i]*P[i]<=b && e!=1;i++) {
            if (e%P[i] == 0) {
                x[++k] = P[i];
                while (e%P[i] == 0)
                    e/=P[i];
            }
        }
        if (e!=1) {
            x[++k] = e;
        }

        memset(w, 0, sizeof(w));
        sol = 0;
        while (!w[0]) {
            j = k;
            while (w[j] == 1) {
                w[j] = 0;
                j--;
            }
            w[j] = 1;
            if (j == 0)
                break;
            nr = 0;
            y = 1;
            for (j=1;j<=k;j++) {
                nr+=w[j];
                if (w[j])
                y *= x[j];
            }
            if (nr&1)
                sol += a/y;
            else
                sol -= a/y;
        }
        if (sol > 0)
            fout<<a-sol<<"\n";
        else
            fout<<a+sol<<"\n";
    }

    return 0;
}