#include <fstream>
#define DIM 1000000
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long A,B;
long long ciur[1000050];
long long prim[100050];
long long divprim[50];
int M,nrprim,nrdiv;
int v[50];
void prime(long long ciur[]){
    for(int i=2;i<=DIM/i;i++)
        if(ciur[i]==0)
            for(int j=i+i;j<=DIM;j+=i)
                ciur[j]=1;
    for(int i=2;i<=DIM;i++)
        if(ciur[i]==0)
            prim[++nrprim]=i;
}
void descompunere(long long B){
    nrdiv=0;
    for(int i=1;i<=nrprim;i++){
        if(prim[i]>B/prim[i])
            break;
        if(B%prim[i]==0){
            divprim[++nrdiv]=prim[i];
            while(B%prim[i]==0)
                B/=prim[i];
        }
    }
    if(B>1)
        divprim[++nrdiv]=B;
}
void resetare(){
    for(int i=1;i<50;i++)
        v[i]=0;
}
void submultimi(long long A){
    resetare();
    int ok=1;
    long long rele=0;
    while(ok){
        long long p=1;
        int nr=0;
        for(int i=1;i<=nrdiv;i++)
            if(v[i]==1){
                p*=divprim[i];
                nr++;
            }
        if(nr!=0)
            if(nr%2!=0)
                rele+=A/p;
            else
                rele-=A/p;
        int i=nrdiv;
        while(i>=1 && v[i]==1){
            v[i]=0;
            i--;
        }
        if(i==0)
            ok=0;
        else
            v[i]=1;
    }
    fout<<A-rele<<endl;
}
int main()
{
    prime(ciur);
    fin>>M;
    for(int m=1;m<=M;m++){
        fin>>A>>B;
        nrdiv=0;
        descompunere(B);
        submultimi(A);
    }
    return 0;
}