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