#include<fstream>
using namespace std;
int i, j, b2, x[40], m[1000003], m2, P[1000003], p, nr2, d;
long long n, b, s, D[40], nr;
ifstream in("pinex.in");
ofstream out("pinex.out");
int main(){
    m[1]=1;
    for(i=2; i<=999999; i++){
        if(m[i]==0){
            P[++p]=i;
            for(j=i+i; j<=1000000; j+=i)
                m[j]=1;
        }
    }
    in>>m2;
    for(;m2--;){
        d=0;
        s=0;
        in>>n>>b;
        b2=b;
        for(i=1; P[i]*(long long)P[i]<=b2; i++){
            if(b%P[i]==0){
                D[++d]=P[i];
                while(b%P[i]==0)
                    b/=P[i];
            }
        }
        if(b!=1)
            D[++d]=b;
        x[0]=0;
        while(x[0]==0){
            j=d;
            while(x[j]==1){
                x[j]=0;
                j--;
            }
            x[j]=1;

            nr=1;
            nr2=0;
            for(i=1; i<=d; i++)
                if(x[i]==1){
                    nr*=D[i];
                    nr2++;
                }
            if(nr2%2==1)
                s+=n/nr;
            else
                s-=n/nr;
        }
        out<<-s<<"\n";
    }
    return 0;
}