#include<cstdio>
#include<vector>
#define tip long long
using namespace std;
vector<tip>v[20],Q;
vector<tip>::iterator it,IT;
int M,nf,j,V[1000004];
tip A,B,i,sol;
void ciur();
int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%d", &M);
    ciur();
    for(;M;M--)
    {
        scanf("%lld%lld", &A, &B);
        v[0].push_back(1);

        for(IT=Q.begin();IT!=Q.end()&&(*IT)*(*IT)<=B;IT++)
        {
            if(B%(*IT)!=0)continue;
            while(B%*IT==0)B/=(*IT);
            for(j=nf;j>=0;j--)
                for(it=v[j].begin();it!=v[j].end();it++)
                    v[j+1].push_back((*it)*(*IT));
            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;
}
void ciur()
{
    int i,j;
    for(i=2;i<=1000000;i++)
        if(!V[i])
        {
            Q.push_back(i);
            for(j=i+i;j<=1000000;j+=i)
                V[j]=1;
        }
}