#include <iostream>
#include <cstdio>
#include <cstring>
#include <bitset>
#define NMAX 1000008
#define pom(x) (((x)%2 == 1) ? 1 : (-1))

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;
   for (int i = 2; i <= NMAX; ++i){
      if (!erathos[i]){
         primeNums[++primeNums[0]] = i;
         for (int j = 2*i; j <= NMAX; j+=i)
            erathos[j] = 1;
      }
   }
}

void combine(int k){
   long long int prod = 1;
   for (int i = 1; i <= k-1; ++i)
      prod *= diviz[sol[i]];
   if (prod != 1)
      res += pom(k-1) * (a / prod);

   if (k > diviz[0])
      return;

   for (int i = sol[k-1] + 1; i <= diviz[0]; ++i){
      sol[k] = i;
      combine(k+1);
   }
}

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(1);
}

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);
      memset(diviz, 0, sizeof(diviz));
      res = 0;
      processData();
      printf("%lld\n", a - res);
   }

   return 0;
}