#include <iostream>
#include <cstdio>
#include <cstring>
#include <bitset>
#define NMAX 1000008

using namespace std;

int m;
long long int a, b;
long long int diviz[NMAX], sol[NMAX], primeNums[NMAX];
bitset<NMAX> viz, erathos;
long long int res;

void findPrimes(){
   erathos = 0;
   primeNums[++primeNums[0]] = 2;
   for (int i = 3; i <= NMAX; i += 2){
      if (!erathos[i]){
         primeNums[++primeNums[0]] = i;
         for (int j = 2*i; j <= NMAX; j+=i)
            erathos[j] = 1;
      }
   }
}

void combine(){
   long long int prod;
   int ones;
   long long int lmax = (1<<diviz[0]);
   for (int i = 1; i <= lmax-1; ++i){
      prod = 1;
      ones = 0;
      for (int j = 1; j <= diviz[0]; ++j){
         if (i & (1 << (j-1))){
            prod *= diviz[j];
            ++ones;
         }
      }
      res = res + ((ones%2==1)?1:(-1)) * a/prod;
   }
}

void findDiviz(){
   for (int i = 1; b > 1 && i <= primeNums[0] && primeNums[i] <= a; ++i){
      if (b % primeNums[i] == 0){
         diviz[++diviz[0]] = primeNums[i];
         while (b > 1 && b % primeNums[i] == 0)
            b /= primeNums[i];
      }
   }
   if (b != 1){
      diviz[++diviz[0]] = b;
   }
}

void processData(){
   findDiviz();
   combine();
}

int main()
{
   freopen("pinex.in", "r", stdin);
   freopen("pinex.out", "w", stdout);

   findPrimes();

   scanf("%d\n", &m);
   for (int i = 1; i <= m; ++i){
      scanf("%lld %lld", &a, &b);
      diviz[0] = 0;
      res = 0;
      processData();
      printf("%lld\n", a - res);
   }

   return 0;
}