#include <bits/stdc++.h>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long cnt, ans, s, a, b, d, k, m, e, p[70];
void bkt(int i) {
    if (i==k+1) {
        if (cnt==0) return ;
        if (cnt%2==1) s+=a/ans;
        else s-=a/ans;
        return ;
    }
    ans*=p[i];
    cnt++;
    bkt(i+1);
    cnt--;
    ans/=p[i];
    bkt(i+1);
}
int main()
{
    fin>>m;
    while (m--) {
        fin>>a>>b;
        d=2, k=0;
        while (d*d<=b) {
            int e=0;
            while (b%d==0) {
                b/=d;
                e++;
            }
            if (e>0) {
                p[++k]=d;
            }
            d++;
        }
        if (b>1) p[++k]=b;
        s=0;
        ans=1;
        bkt(1);
        fout<<a-s<<'\n';
    }
    return 0;
}