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

int m,p,pr;
int a[500];
int solve(ll A, ll b) {
    int p=2; int rs=0; pr=0;
    while (b>1 && 1LL*p*p<=b) {
        int k=0;
        while (b%p==0) {
            ++k; b/=p;
        }
        if (k) a[++pr]=p; ++p;
    }
    if (b>2) a[++pr]=b;

    for (int i=1; i<(1<<pr); ++i) {
        int k=0; int nr=1;
        for (int j=0; (1<<j)<=i; ++j) {
            if (i & (1<<j)) {
                ++k; nr*=a[j+1];
            }
        }
        rs+=A/nr*(k%2?1:-1);
    }
    return rs;
}

int main() {
    ifstream cin("pinex.in");
    ofstream cout("pinex.out");
    cin>>m;

    while (m--) {
        ll a,b; cin>>a>>b;
        cout<<a-solve(a,b)<<'\n';
    }

    return 0;
}