#include <fstream>
#define DIM 1000001
#define PMAX 100001
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long q,a,b,k,cnt,p,sol;
int v[PMAX],d[PMAX],x[13];
bool c[DIM];

void backtrack(int k) {
    for (int i=x[k-1]+1;i<=cnt;i++) {
        x[k]=i;
        p*=d[i];
        if (k%2==0)
            sol-=a/p;
        else
            sol+=a/p;
        if (k<cnt)
            backtrack(k+1);
        p/=d[i];
    }
}

int main() {
    for (int i=2;i<DIM;i++)
        if (c[i]==0) {
            v[++k]=i;
            for (int j=2*i;j<DIM;j+=i)
                c[j]=1;
        }
    fin>>q;
    while (q--) {
        fin>>a>>b;
        cnt=0;
        for (int i=1;i<=k && 1LL*v[i]*v[i]<=b;i++)
            if (b%v[i]==0) {
                d[++cnt]=v[i];
                while (b%v[i]==0)
                    b/=v[i];
            }
        if (b!=1)
            d[++cnt]=b;
        sol=0;
        p=1;
        backtrack(1);
        fout<<a-sol<<"\n";
    }
    return 0;
}