#include <cstdio>
#include <cmath>
using namespace std;
int long long vf, i, PrimeList[1000005], M, BList[1000005], vfb;
int long long A, B, P;
bool Ciur[1000005];
int long long Calculate(int long long A, int long long B){
    int long long d=0; int long long i, p, j, P, S=0, k; vfb=0;
    while(B>1){d++;
        if(!(B%PrimeList[d])){while(!(B%PrimeList[d]))B/=PrimeList[d];
                              BList[++vfb]=PrimeList[d];}
        if(d>=sqrt(B) && B>1) {BList[++vfb]=PrimeList[d]; B=1;}
    }
    for(i=1; i<=(1<<vfb)-1; i++){p=i; P=1; k=0;
    for(j=1; j<=vfb; j++){
      if(p&1) {P*=BList[j]; k++;}
      p/=2;
    }
    P=A/P;
    if(k%2)
     S+=P;
     else S-=P;
    }
    return S;
}
void Peridot(){
    int i, j; bool k;
    for(i=2; i<1000000; i++){
        if(!Ciur[i]){for(j=2*i; j<1000000; j+=i)Ciur[j]=1;
                     PrimeList[++vf]=i;

    }
}
}
int main()
{
    Peridot();
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    scanf("%d", &M);
    for(i=1; i<=M; i++){
        scanf("%lld%lld", &A, &B);
        P=Calculate(A, B);
        printf("%lld%c", A-P, '\n');
    }
    return 0;
}