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

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

#define int long long

int pm1(int k){
    if(k%2==0) return 1;
    return -1;
}

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

void getDivs(int b, vector<int>& divs){
    divs.clear();
    for(int d:prime){
        int p=0;
        for(;b%d==0; b/=d){
            ++p;
        }
        if(p) divs.push_back(d);
        if(b==1) break;
    }
    if(b!=1) d.push_back(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 solve(){
    fin>>a>>b;
    getDivs(b,divs);
    ans=0;
    for(int k=1; k<=(int)divs.size();++k){
        backt(1, divs.size(), k);
    }
    fout<<a-ans<<"\n";
}


void ciurPrime(){
    const int MX=1e6;
    bitset<MX> c=move(bitset<MX>().set());
    for(int i=0;i<MX;i+=2)
        c[i]=0;
    c[0]=c[1]=0;
    c[2]=1;
    for(int i=3;i<MX;i+=2){
        if(c[i])
            for(int j=i*3; j<MX; j+=i*2)
                c[j]=0;
    }
    prime.push_back(2);
    for(int i=3;i<MX;i+=2){
        if(c[i]) prime.push_back(i);
    }
}

int32_t main(){
    ciurPrime();
    // for(int d:prime){
    //     db(d);
    //     if(d>140) break;
    // }
    int t; fin>>t;
    while(t--){
        solve();
    }
}