#include <fstream>
#define NMAX 1000001
using namespace std;
ifstream fi("pinex.in");
ofstream fo("pinex.out");
int pr[NMAX],divp[1000];
long long  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;
            long long t=0;    //aflarea factorilor primi a numarului 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)divp[++t]=pr[j];
                j++;
            }
            if(x>1)divp[++t]=x;
            //for(j=1;j<=t;j++)fo<<div[j]<<" ";fo<<endl;
            //generam submultimi de t elemente
            long long sol=0,lim=1<<t;  //sol este =a/prod. de div. primi
            for(i=1;i<lim;i++)
            {
                long long  semn=0,term=1;//term - produs de factori primi
                for(j=1;j<=t;j++)
                    if(i&(1<<(j-1))){term=term*divp[j];semn++;}
                if(semn%2==1)sol+=a/term;
                else sol-=a/term;

            }
            fo<<a-sol<<'\n';//scad din a factorii neprimi cu b =>fact. primi
    }
    return 0;
}