#include<cstdio>
#include<vector>
using namespace std;
vector <long long> v;
int main(){
    long long a,b,d,cb,nr,sol,prod;
    int m,i,ci,ind,num,j;
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%d",&m);
    for(i=1;i<=m;i++){
        scanf("%lld%lld",&a,&b);
        d=2;
        cb=b;
        while(d*d<=cb){
            if(cb%d==0){
                v.push_back(d);
                while(cb%d==0)
                    cb/=d;
            }
            d++;
        }
        if(cb!=1)
            v.push_back(cb);
        nr=(1<<v.size())-1;
        sol=0;
        for(j=1;j<=nr;j++){
            ci=j;
            ind=v.size()-1;
            prod=1;
            num=0;
            while(ind>=0){
                if(ci%2==1){
                    prod*=v[ind];
                    num++;
                }
                ci/=2;
                ind--;
            }
            if(num%2==1)
                sol+=a/prod;
            else
                sol-=a/prod;
        }
        printf("%d\n",a-sol);
        while(!v.empty())
            v.pop_back();
    }
    return 0;
}