#include <fstream>
#include <bitset>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int cont,n,factor[100000],t,sol,prim[1000010],aux,p,nrprim,a,b;

bitset<1000010>ciur;


int main(){
    nrprim++;
    prim[nrprim]=2;
    for (int i=3;i<=1000000;i+=2) {
        if (ciur[i]==0){
            nrprim++;
            prim[nrprim] =i;
            for (int j=i+i;j<=1000000;j+=i){
                ciur[j]=1;
            }


        }

    }
    fin>>t;
    for(int i=1;i<=t;i++){
        fin>>a>>b;
        n=b;
        cont=0;

        for(int i=1;n!=1 && prim[i]*prim[i]<=n;i++){
            if(n%prim[i]==0){
                int pr=prim[i];
                cont++;
                factor[cont]=pr;
                while(n%pr==0 ){
                    n=n/pr;
                }


            }

        }
        if(n!=1){
            cont++;
            factor[cont]=n;
        }

        int sol=a;
        for(int i=1;i<(1<<cont);i++){
            p=1;
            aux=0;
            for(int j=0;j<cont;j++){
                if((1<<j)&i){
                    p=p*factor[j+1];
                    aux++;
                }
            }
            if(aux%2==1){
                aux=-1;
            }
            else{
                aux=1;
            }
               sol+=aux*a/p;
        }


        fout<<sol<<"\n";
        for(int i=1;i<=cont;i++){
            factor[i]=0;
        }

    }





}