#include<fstream>
#include<algorithm>
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
typedef long long ll;
int m,k,p[100005];
ll a,b,x[1005];
bool ciur[1000005];
int main(){
    ciur[0]=ciur[1]=1;
    for(int i=2;i<=1000000;i+=2)
        ciur[i]=1;
    p[++k]=2;
    for(int i=3;i<=1000000;i+=2)
        if(!ciur[i]){
            p[++k]=i;
            for(int j=i;j<=1000000;j+=i) ciur[j]=1;
        }
    cin>>m;
    while(m--){
        cin>>a>>b; k=0;
        for(int d=1;1LL*p[d]*p[d]<=b;d++)
            if(b%p[d]==0){
                x[++k]=p[d];
                while(b%p[d]==0) b/=p[d];
            }
        if(b>1) x[++k]=b;
        ll ans=a,prod,nr;
        for(int i=1;i<(1<<k);i++){
            nr=0; prod=1;
            for(int j=0;j<k;j++)
                if((1<<j)&i){
                    prod=prod*1LL*x[j+1];
                    ++nr;
                }
            if(nr%2==1) nr=-1;
            else nr=1;
            ans=ans+1LL*nr*a/prod;
        }
        cout<<ans<<'\n';
    }
}