#include<bits/stdc++.h>
#define N 1000005
#define int long long
using namespace std;

bool viz[N];
vector<int> V, c;
int n,pr,t, rs;

int get(int n, int a) {
    return (a)/n;
}
int32_t main() {
    ifstream cin("pinex.in");
    ofstream cout("pinex.out");
    for (int i=2; i*i<=1e6; i++) {
        if (!viz[i]) {
            for (int j=i*i; j<=1e6; j+=i) viz[j]=1;
            V.push_back(i);
        }
    }

    cin>>t;
    while (t--) {
        int a,b; cin>>a>>b;

        int i=0;
        while (i<V.size() && V[i]*V[i]<=b) {
            int k=0;
            while (b%V[i]==0) {b/=V[i], k++;}
            if (k) c.push_back(V[i]), ++pr;
            ++i;
        }

        if (b>1) c.push_back(b), ++pr;

        for (int i=1; i<(1<<pr); i++) {
            int nr=1, k=0;
            for (int j=0; (1<<j)<=i; j++) {
                if ((1<<j) & i) {
                    nr = nr*c[j]; ++k;
                }
            }

            if (k&1) rs+=get(nr, a);
            else rs-=get(nr, a);
        }

        cout<<a-rs<<'\n'; c.clear(); rs=pr=0;
    }


    return 0;
}