#include<fstream>
#include<math.h>
#define val 1000010

using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

bool V[val];
int i,k,nr,semn,p,Prim[100010],T,j;
long long A,B,divizori[20],prod,total;
double rad;


int main(){

    f>>T;
    Prim[++k]=2;
    for(i=3;i<=val;i+=2){
        if(V[i]==0){
            Prim[++k]=i;
            for(j=i;j<=val;j+=i)
                V[j]=1;
        }
    }

    while(T--){
        f>>A>>B;
        nr=0;total=0;
        rad=sqrt(B);
        for(i=1;i<=k&&(Prim[i]<=rad);i++){
            if(B%Prim[i]==0){
                divizori[++nr]=Prim[i];
                while((B%Prim[i])==0)
                    B/=Prim[i];
            }
        }
        if(B!=1)
            divizori[++nr]=B;
        p=1;
        while( p!=(1<<(nr)) ){
            semn=0;prod=1;
            for(i=0;i<nr;i++){
                if((p&(1<<i))!=0){
                    semn++;
                    prod*=divizori[i+1];
                }
            }
            if(semn%2==1)
                total+=A/prod;
            else
                total-=A/prod;
            p+=1;
        }
        g<<A-total<<"\n";
    }

    return 0;
}