#include <fstream>
#include <bitset>
using namespace std;
const long long MAX=10000;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int m,pmax,gata,nr,j;
long long a,b,pi,sigma;
bitset<MAX> prim;
bitset<MAX> s;
long long v[100000],p[1000];
void ciur(){
    v[0]=2;
    pmax=1;
    for(int i=3;i<MAX;i+=2){
        if(prim[i]==0){
                v[pmax++]=i;
        for(int j=i*i;j<MAX;j+=i+i) prim[j]=1;

    }
}
}
int main(){
    fin>>m;
    ciur();
    for(int k=1;k<=m;++k){
        fin>>a>>b;
        pmax=0;
        gata=0;
        for(int i=0;v[i]<=b;++i){
            if(b%v[i]==0){
                p[pmax++]=v[i];
                while(b%v[i]==0) b/=v[i];
            }

        }
        while(!gata){
                pi=1;
                nr=0;
            for(int i=0;i<pmax;++i) if(s[i]){
                    pi*=p[i];
                    nr++;
            }
            if(nr==0)
                sigma=0;
            else{
            if(nr%2==1)
                sigma+=a/pi;
            else
                sigma-=a/pi;
            }
            for( j=0;j<pmax && s[j];++j) s[j]=0;
            if(j==pmax) gata=1;
                else s[j]=1;

        }
        fout<<a-sigma<<'\n';

    }

    return 0;
}