#include<fstream>
using namespace std;
int n, i, j, b, b2, s, x[20], m[1000003], m2, P[1000003], p, nr, nr2, d, D[20];
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]*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;
}