#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long t,a,b,i,j,k,x,nr,sol,p[100001],v[101];
bool ciur[1000001];
int main() {
    k=0;
    for (i=2;i<=1000000;i++)
        if (ciur[i]==0) {
            p[++k]=i;
            for (j=2*i;j<=1000000;j+=i)
                ciur[j]=1;
        }
    fin>>t;
    while (t--) {
        fin>>a>>b;
        x=b;
        k=0;
        for (i=1;p[i]*p[i]<=b && x!=1;i++)
            if (x%p[i]==0) {
                v[++k]=p[i];
                while (x%p[i]==0)
                    x/=p[i];
            }
        if (x!=1)
            v[++k]=x;
        sol=0;
        for (i=1;i<(1<<k);i++) {
            nr=0;
            x=1;
            for (j=0;j<k;j++)
                if ((1<<j)&i) {
                    x*=v[j+1];
                    nr++;
                }
            if (nr%2==0)
                sol-=a/x;
            else
                sol+=a/x;
        }
        if (sol>0)
            fout<<a-sol<<"\n";
        else
            fout<<a+sol<<"\n";
    }
    return 0;
}