#include <stdio.h>

using namespace std;

FILE*f=fopen("pinex.in","r");
FILE*g=fopen("pinex.out","w");

#define MAX 1000000
#define ll long long
ll nrp=0;
ll pr[MAX+100],p[MAX+100];

void ciur(){
    ll d=2,i=2;
    for (d=2;d<=MAX;d++)
        if (!pr[d]){
        pr[++nrp]=d;
        for (i=d*d;i<=MAX;i+=d)
            pr[i]=1;
    }

}

int main()
{
    ll m,a,b,nr,x,i,s,z,j,prod;
    fscanf(f,"%lld",&m);
    ciur();
    while (m>0){
        m--;
        fscanf(f,"%lld%lld",&a,&b);
        x=b;
        i=1;nr=0;s=0;
        while (x>1){
            if (!(x%pr[i])){
                p[++nr]=pr[i];
                while (!(x%pr[i])) x/=pr[i];
            }
            i++;
        }
        nr=1<<nr;
        for (i=1;i<nr;i++){
            z=0;prod=1;
            for (j=0;(1<<j)<=i;j++)
                if (i&(1<<j)) {z++;prod*=p[j+1];}
            if (z%2) z=1;
            else z=-1;
            s+=(a/prod)*z;
        }
        fprintf(g,"%lld\n",a-s);
    }
    fclose(f);
    fclose(g);
    return 0;
}