#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll
#define div divizori
ifstream fin("pinex.in"); ofstream fout("pinex.out");
#define cin fin
#define cout fout
int m ,a , b;
bool sv[1000010];
vector<int> pr;
vector<int> npr;
vector<int> div;



void back_track(int pos, int d, int sz){
if(pos>=div.size()){return;}
int nxt=1;
int d0=d;
int gcd=div[pos];
if(gcd>d0){swap(gcd, d0);}

while(gcd>0){
    int t=gcd;
    gcd=d0%gcd;
    d0=t;
}
gcd=d0;
nxt=(d*div[pos])/gcd;

int oc=a/nxt;
npr[sz+1]+=oc;
back_track(pos+1, d, sz);
back_track(pos+1, nxt, sz+1);
}





int32_t main(){
INIT
sv[1]=true;
for(int i=2; i<=1000000; i++){
    if(sv[i]==false){
            pr.pb(i);
        for(int j=2*i; j<=1000000; j+=i){
            sv[j]=true;
        }
    }
}






cin>>m;
while(m--){
    cin>>a>>b;
    npr.assign(60, 0);
    div.clear();
    for(int i=0; i<pr.size() && pr[i]<=b; i++){
        if( (b%pr[i])==0){
                div.pb(pr[i]);
            while( (b%pr[i])==0){
                b/=pr[i];
            }
        }
    }
    if(b>1){
        div.pb(b);
    }
    back_track(0, 1, 0);



    int un=0;
    for(int i=1; i<=div.size(); i++){
        if(i%2==1){
            un+=npr[i];
        }
        else{
            un-=npr[i];
        }
    }


    cout<<a-un<<"\n";
}



return 0;
}