#include<cstdio>
#include<iostream>
#include<bitset>
#define tip long long
using namespace std;
bitset<500010> p;
long long A,B,*F,P[80000],Q[100],S;
int t,L;
void ciur(),back(tip,int,tip);
int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    ciur();
    cin>>t;
    for(;t;t--)
    {
        cin>>A>>B;L=0;S=0;
        for(F=P;*F;F++)
        {
            if(*F**F>B)break;
            if(B%*F)continue;
            Q[++L]=*F;
            while(B%*F==0)B/=*F;
        }
        if(B>1)Q[++L]=B;
        back(1,1,1);
        cout<<S<<'\n';
    }
    return 0;
}
void ciur()
{
    int i,j,k,n=0;
    P[0]=2;
    for(k=1,i=3;k<500;k++,i+=2)
        if(!p[k])
        {
            P[++n]=i;
            for(j=2*k*k+2*k;j<=500000;j+=i)p[j]=1;
        }
    for(k=500,i=1001;k<=500000;k++,i+=2)
        if(!p[k])
            P[++n]=i;
}
void back(tip D,int U,tip X)
{
    if(U==L+1){S+=X*A/D;return;}
    back(D,U+1,X);
    back(D*Q[U],U+1,-X);
}