/*#include <fstream>

using namespace std;

ifstream fin ("submultimi.in");
ofstream fout("submultimi.out");
int x[30], n, nr;
/// generez toate sirurile de lungime n cu 0 si 1
void back(int pas) {
    if (pas > n) {
        nr++;
        for (int i=1;i<=n;i++)
            if (x[i] == 1)
                fout<<i<<" ";
        if (nr != 1)
            fout<<"\n";
    } else {
        for (int i=0;i<=1;i++) {
            x[pas] = i;
            back(pas+1);
        }
    }
}

int main () {
    fin>>n;
    back(1);

    return 0;
}
*/

#include <fstream>
#include <cmath>
using namespace std;
ifstream fin ("pinex.in");
ofstream fout ("pinex.out");
int t,x[100010],a[1000010],T,prim[100010],div[100010],A,B,i,k,j;
long long sol;
void back (int nivel){
    if(nivel>t){
        long long p=1;
        int cnt=0;
        for(int i=1;i<=t;i++)
            if(x[i]){
                cnt++;
                p*=div[i];
            }
        if(cnt%2==0)
            sol-=A/p;
        else
            sol+=A/p;
    }
    else{
        for(int i=0;i<=1;i++){
            x[nivel]=i;
            back(nivel+1);
        }
    }
}

int main(){
    for(i=2;i<=1000001;i++)
      a[i]=1;
    for(i=2;i*i<=1000001;i++)
        if(a[i]){
            prim[++k]=i;
            for(j=i;j<=1000001/i;j++)
                a[i*j]=0;
        }

    fin>>T;
    for(;T--;T>0){
        fin>>A>>B;
        for(i=1;i<=k && prim[i]<=B;i++)
            if(B%prim[i]==0)
                div[++t]=prim[i];
        sol=0;
        back(1);
        fout<<A-abs(sol)<<"\n";
    }
    return 0;
}