#include <fstream>
#define dim (int)(1e6+1)
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
int q,nrp[100001],k,d[100001];
long long a,b,sol,nr;
bool ciur[dim];
void bck(int k,int last){
    if(k==d[0]+1){
        if(d[0]%2==0)
            sol-=a/nr;
        else
            sol+=a/nr;
        return ;
    }
    if(k!=1){
        if((k-1)%2==0)
            sol-=a/nr;
        else
            sol+=a/nr;
    }
    for(int i=last+1;i<=d[0];i++){
        nr*=d[i];
        bck(k+1,i);
        nr/=d[i];
    }
}
signed main()
{
    cin>>q;
    for(int i=2;i<dim;i++)
        if(!ciur[i]){
            nrp[++k]=i;
            for(int j=i*2;j<dim;j+=i)
                ciur[j]=1;
        }
    while(q--){
        cin>>a>>b;
        d[0]=0;
        sol=0;
        nr=1;
        if(b==1){
            cout<<a<<'\n';
            continue;
        }
        for(int i=1;1LL*nrp[i]*nrp[i]<=b;i++)
            if(b%nrp[i]==0){
                d[++d[0]]=nrp[i];
                while(b%nrp[i]==0)
                    b/=nrp[i];
            }
        if(b!=1)
            d[++d[0]]=b;
        bck(1,0);
        cout<<a-sol<<'\n';
    }
    return 0;
}