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

using namespace std;

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

int isPrime(int x){
   if (x < 2 || x > 2 && x % 2 == 0)
      return 0;
   for (int d = 3; d * d <= x; d += 2)
      if (x % d == 0)
         return 0;
   return 1;
}

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

void combine(int k){
   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 processData(){
   findDiviz();
   combine(1);
}

void pre(){
   for (int i = 2; i <= NMAX; ++i)
      if (isPrime(i))
         primeNums[++primeNums[0]] = i;
}

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

   pre();

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

   return 0;
}