#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,nr,sol;
int v[PMAX],d[13];
bool c[DIM];
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;
        for (int i=1;i<(1<<cnt);i++) {
            p=1;
            nr=0;
            for (int j=0;j<cnt;j++)
                if ((1&(i>>j))==1) {
                    p*=d[j+1];
                    nr++;
                }
            if (nr%2==0)
                sol-=a/p;
            else
                sol+=a/p;
        }
        fout<<a-sol<<"\n";
    }
    return 0;
}