#include<bits/stdc++.h>
#define nl '\n'
using namespace std;
const string file="pinex";
ifstream f(file+".in");
ofstream g(file+".out");
//#define f cin
//#define g cout
#define ll long long
int t;
ll a,b;
vector<ll>fp(ll b) {
    vector<ll>p;
    ll d=2,pw;
    while (b>1) {
        pw=0;
        while (b%d==0) ++pw,b/=d;
        if (pw) p.push_back(d);
        ++d;
        if (d*d>b) d=b;
    }
    return p;
}
ll pinex(ll a, vector<ll>p) {
    ll r=0;
    for (ll msk=1; msk<(1<<p.size()); ++msk) {
        long long semn=-1,pw=1;
        for (int i=0; i<p.size(); ++i) {
            if (msk&(1<<i)) {
                semn*=-1;
                pw*=p[i];
            }
        }
        r+=semn*(a/pw);
    }
    return r;
}
int main(){
    f>>t;
    while (t--) {
        f>>a>>b;
        vector<ll>p=fp(b);
        g<<a-pinex(a,p)<<nl;
    }
    system("pause");
    return 0;
}