#include <bits/stdc++.h>
#define db(x) cerr << #x <<":"<<x<<"  "
using namespace std;

ifstream fin ("pinex.in");
ofstream fout("pinex.out");

int pm1(int k){
    if(k%2==0) return 1;
    return -1;
}
void getDivs(int b, vector<int>& divs){
    divs.clear();
    for(int d=2;d*d<=b;++d){
        int p=0;
        while(b%d==0){
            b/=d; ++p;
        }
        if(p) divs.push_back(d);
    }
    if(b!=1) divs.push_back(b);
}


int st[100044], f[100044];
vector<int> divs;
int ans=0;
int a, b;

void backt(int k, const int MX, const int SZ){
    if(k-1==SZ){
        // int lans=a*pm1(SZ-1);
        int imp=1;
        for(int i=1;i<k;++i){
            imp*=divs[st[i]-1];
            // lans/=divs[st[i]-1];
            // cout<<divs[st[i]-1]<< ' ';
        }
        ans+=a*pm1(SZ-1)/imp;
        return ;
    }
    for(int i=st[k-1]+1;i<=MX;++i){
        if(f[i]==0){
            f[i]=1; st[k]=i;
            backt(k+1, MX, SZ);
            f[i]=0;
        }
    }
}

void reset(){
}

void solve(){
    reset();
    fin>>a>>b;
    getDivs(b,divs);
    // int ans=a;
    ans=0;
    for(int k=1; k<=(int)divs.size();++k){
        backt(1, divs.size(), k);
        // int lans=100*pm1(k);
        // for(int i=0;i<divs.size()-k;++i)
        //     lans/=divs[st[i]];
        // ans+=lans;
    }
    // for(int d:divs) cout<<d<<" ";
    // cout<< "\n";
    fout<<a-ans<<"\n";
}

int32_t main(){
    int t; fin>>t;
    while(t--){
        solve();
    }
}