#include<bits/stdc++.h>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int T,A,B,l,fp[1000001];
long long nr;
void descfactpr(int x){
    int n=x,f=2;
    l=0;
    while(f*f<=n){
        if(x%f==0){
            fp[++l]=f;
            while(x%f==0)x/=f;
        }
        if(f==2)++f;
        else f+=2;
    }
    if(x>1)fp[++l]=x;
}
int main()
{
    f>>T;
    while(T--){
        f>>A>>B;
        descfactpr(B);
            long long sol=A;
            for(int i=1;i<(1<<l);++i){
                int num=0;
                long long p=1;
                for(int j=0;j<=l;++j)
                    if((1<<(j-1))&i)
                        ++num,p*=fp[j];
                if(num%2)p*=-1;
                sol+=A/p;
            }
            g<<sol<<'\n';
    }
    return 0;
}