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

int m,n,k,rs,k3, a[200], b[N+5], viz[N+5];

int32_t main() {
    ifstream cin("pinex.in");
    ofstream cout("pinex.out");
    cin>>m;
    for (int i=2; i*i<=N; ++i) {
        if (!viz[i]) {
            for (int j=i*i; j<=N; j+=i) viz[j]=1;
        }
    }
    for (int i=2; i<=N; ++i) {
        if (!viz[i]) b[++k3]=i;
    } b[k3+1]=1e9;
    while (m--) {
        int A,B; cin>>A>>n;
        int i=1;
        k=0; rs=0;
        while (b[i]*b[i]<=n) {
            if (n%b[i]==0) {
                a[++k]=b[i];
                while (n%b[i]==0) n/=b[i];
            } ++i;
        }
        if (n>1) a[++k]=n;
        for (int i=1; i<(1<<k); ++i) {
            int nr=1,k2=0;
            for (int j=0; (1<<j)<=i; ++j) {
                if ((1<<j) & i) nr*=(a[j+1]), ++k2;
            }
            rs+=A/nr*(k2&1?1:-1);
        }
        cout<<A-rs<<"\n";
    }
    return 0;
}