#include<fstream>
using namespace std;
long long x,numitor,nr1,card,a,b,i,j,k,l,prim[100100],n,nr;
bool ch[1000100];
long long p[100100];
int main(){
    ifstream f("pinex.in");
    ofstream g("pinex.out");
    for (i=2;i<=100000/2;i++){
        if (ch[i]==false){
            for (j=2;j<=100000/i;j++)
                ch[i*j]=true;
        }
    }
    for (i=2;i<=100000;i++)
        if (ch[i]==false) {
            nr++;
            prim[nr]=i;
        }
    f>>n;
    for (l=1;l<=n;l++){
        f>>a>>b;
        nr=1;k=0;card=0;
        while (b!=1){
            if (b%prim[nr]==0) {
                k++;
                p[k]=prim[nr];
				while (b%prim[nr]==0)
                      b=b/p[k];
            }
            nr++;
        }
        for (i=1;i<1<<k;i++){
            x=i;
            numitor=1;
            nr1=0;
            for (j=1;j<=k;j++){
                if (x%2==1){
                    numitor=numitor*p[j];
                    nr1++;
                }
                x=x/2;
            }
            if (nr1%2==1) card=card+a/numitor;
            else card=card-a/numitor;
        }
        g<<a-card<<"\n";
    };
    return 0;
}