#include <fstream>
#include <bitset>
using namespace std;

#define MAX 1000001

ifstream fin("pinex.in");
ofstream fout("pinex.out");

int m,ct,pmax,nr,kk;
long long a,b,pi,sum;
long long p[300000];
long long f[60];
bitset <1000001> prim;
bitset <60> s;

void ciur(){
    p[++ct]=2;
    for(int i=3;i<=MAX;i+=2){
        if(!prim[i]){
            p[++ct]=i;
            if(i<=1000)
                for(int j=i*i;j<=MAX;j+=i+i) prim[j]=1;
        }
    }
}

int main(){
    ciur();
    fin>>m;
    for(int t=1;t<=m;++t){
        fin>>a>>b;
        pmax=0;
        sum=0;
        if(b==1) kk=1; //caz special
        for(int i=1;i<=ct;++i){
            if(b%p[i]==0){
                f[++pmax]=p[i];
                while(b%p[i]==0) b/=p[i];
            }
        }
        if(b>1) f[++pmax]=b;
        int ok=1;
        s[1]=1;
        while(ok){
            pi=1;
            nr=0;
            for(int i=1;i<=pmax;++i)
                    if(s[i]) pi*=f[i],nr++;
            if(nr%2==1) sum+=a/pi;
            else sum-=a/pi;
            int j;
            for(j=1;j<=pmax && s[j];++j) s[j]=0;
            if(j==pmax+1) ok=0;
            else s[j]=1;
        }
        long long sol=a-sum;
        if(kk) fout<<a<<'\n',kk=0; // pentru cazul b==1
        else
            fout<<sol<<'\n';

    }

    return 0;
}