#include <fstream>
std::ifstream cin("pinex.in");
std::ofstream cout("pinex.out");
#define ll long long
#define maxn 1000000
ll m,a,b,facts[40];

ll solve(ll a,ll b){
    ll prod=1,sol=a;
    int t=0,d=2,nr;
    while(b>1){
        if(b%d==0){
            facts[++t]=d;
            while(b%d==0)
                b/=d;
        }
        if(d*d>b&&b>1){
            facts[++t]=b;
            b=1; break;
        }
        if(d==2) d++;
        else d+=2;
    }
    for(int i=1;i<(1<<t);i++){
        nr=0,prod=1;
        for(int j=0;j<t;j++)
            if((1<<j)&i){
                prod=1LL*prod*facts[j+1];
                nr++;
            }
        if(nr%2)nr=-1;
        else nr=1;
        sol+=(a/prod*nr);
    }
    return sol;
}


int main()
{
    cin>>m;
    for(;m--;){
        cin>>a>>b;
        cout<<solve(a,b)<<'\n';
    }
    return 0;
}