#include <fstream>
#define NMAX 1000001
using namespace std;
ifstream fi("pinex.in");
ofstream fo("pinex.out");
int pr[NMAX],div[1000];
int i,j,m,k,p;
long long a,b,x;
int main()
{
    //ciur pana la 10^6
    for(i=2;i<NMAX;i++)
    if(pr[i]==0){
        pr[++k]=i;
        for(j=2*i;j<NMAX;j=j+i)pr[j]=1;
    }
    fi>>m;
    for(int z=1;z<=m;z++){
            fi>>a>>b;
            int t=0;    //aflarea factorilor primi a lui b
            x=b;j=1;   //div[1],div[2].....div[t]
            while(x>1 and pr[j]*pr[j]<=x)
            {
                p=0;
                while(x%pr[j]==0){p++;x=x/pr[j];}
                if(p)div[++t]=pr[j];
                j++;
            }
            if(x>1)div[++t]=x;
            //for(j=1;j<=t;j++)fo<<div[j]<<" ";fo<<endl;
            //generam submultimi de t elemente
            int lim=1<<t;
            long long sol=0;
            for(i=1;i<lim;i++)
            {
                int putere=0,term=1;
                for(j=1;j<=t;j++)
                    if(i&(1<<(j-1))){term=term*div[j];putere++;}
                if(putere%2==1)sol+=a/term;
                else sol-=a/term;

            }
            fo<<a-sol<<'\n';
    }
    return 0;
}