#include <bits/stdc++.h>

using namespace std;
ifstream in("pinex.in");
ofstream out("pinex.out");

bool divide(long long &x, long long divide){
  if(x % divide != 0)
      return false;
  do{
      x /= divide;
  }while(x % divide == 0);
  return true;
}

void descompunere(long long v[], long long &n, long long x){
  n = 0;
  for(long long d = 2; d <= sqrt(x); d++){
      if(divide(x,d))
          v[n++] = d;
  }
  if(x != 1)
      v[n++] = x;
}

long long v[100000];
long long primeB(long long a,long long b){
  long long n, sum=0;
 
  descompunere(v,n,b);

  for (int sets=1 ;sets<(1<<n);sets++){
        int nrbits=0,prod=1;

        for (int j=0;j<31;j++){
            int mask = 1<<j;


            if (mask & sets)
            {
                nrbits++;
                prod=prod * v[j];
            }

        }
        if (nrbits%2==0)
        {
            sum-=a/prod;
        }
        else{
             sum+=a/prod;
        }

  }
  return a-sum;
}
int main () {
  long long a,b,n;
  in >> n;
  for (int i=1;i<=n;i++){
    in >> a >> b;

    out << primeB(a,b) << "\n";
  }

  return 0;
}