#include<cstdio>
#include<vector>
#define tip long long
using namespace std;
vector<tip>v[20];
vector<tip>::iterator it;
int M,nf,j;
tip A,B,i,sol;
int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%d", &M);
    for(;M;M--)
    {
        scanf("%lld%lld", &A, &B);
        v[0].push_back(1);
        if(B%2==0)
        {
            nf++;
            while(B%2==0)
               B/=2;
            v[1].push_back(2);
        }
        for(i=3;i*i<=B;i+=2)
        {
            if(B%i!=0)continue;
            while(B%i==0)B/=i;
            for(j=nf;j>=0;j--)
                for(it=v[j].begin();it!=v[j].end();it++)
                    v[j+1].push_back((*it)*i);
            nf++;
        }
        if(B>1)
        {
            for(j=nf;j>=0;j--)
                for(it=v[j].begin();it!=v[j].end();it++)
                    v[j+1].push_back((*it)*B);
            nf++;
        }

        sol=A;
        for(j=1;j<=nf;j+=2)
            for(it=v[j].begin();it!=v[j].end();it++)
                sol-=A/(*it);
        for(j=2;j<=nf;j+=2)
            for(it=v[j].begin();it!=v[j].end();it++)
                sol+=A/(*it);
        for(j=0;j<=nf;j++)v[j].resize(0);
        nf=0;
        printf("%lld\n", sol);
    }

    return 0;
}