#include <fstream>
#include <bitset>
#define DIM 1000002
using namespace std;

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

bitset <DIM> v;
bitset <70> s;
long long M,mask,A,B,prim[DIM],N,a[DIM],k;
void ciur(){
    v[1]=v[0]=1;
    for(int i=2;i<=DIM;i++){
        if(!v[i]){
                prim[++N]=i;
            for(int j=i+i;j<=DIM;j+=i)
                v[j]=1;
        }
    }
}
int main(){
    ciur();
    fin>>M;
    while(M--){
        fin>>A>>B;
        k=0;
        for(int i=1;i<=N && prim[i]<B;i++){
            if(B%prim[i]==0){
                a[++k]=prim[i];
                while(B%prim[i]==0)
                    B/=prim[i];
            }
        }
        if(B>1)
            a[++k]=B;
        s.reset();
        long long sol=0;
        s[k]=1;
        while(!s[0]){
            int j=k;
            int par=0;
            long long produs=1;
            for(int i=1;i<=k;i++)
                if(s[i]){
                    par++;
                    produs*=a[i];
                }
            if(par%2)
                sol+=A/produs;
            else
                sol-=A/produs;
            while(s[j]){
                s[j]=0;
                j--;
            }
            s[j]=1;
        }
        fout<<A-sol<<"\n";
    }
    fin.close();fout.close();
    return 0;
}