#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream in("pinex.in");
ofstream out("pinex.out");
int main() {
    int t;
    in>>t;
    const int N=1000006;
    vector<int>f(N),pr;
    for(int i=2; i<N; ++i){
        if(!f[i]){
            pr.push_back(i);
            for(int j=i+i; j<N; j+=i){
                f[j]=1;
            }
        }
    }
    while(t--){
        ll a, b, k=0;
        in>>a>>b;
        vector<ll>v;
        while(b>1){
            if(b%pr[k]==0){
                v.push_back(pr[k]);
                while(b%pr[k]==0){
                    b/=pr[k];
                }
            }
            if(pr[k]*pr[k]>b && b>1){
                v.push_back(b);
                b=1;
            }
            k++;
        }
        ll s=0;
        for(ll i=1; i<(1LL<<v.size()); i++){
            ll nr=0, x=1;
            for(int j=0; j<(int)v.size(); ++j){
                if(i&(1LL<<j)){
                    nr++;
                    x*=v[j];
                }
            }
            s+=(nr%2==1?1:-1)*(a/x);
        }
        out<<a-s<<"\n";
    }
    return 0;
}