#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 div[NMAX], sol[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 findDiv(){
   for (int i = 2; i <= b; ++i){
      if (isPrime(i) && (b % i == 0)){
         div[++div[0]] = i;
      }
   }
}

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

   if (k > div[0])
      return;

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

void processData(){
   findDiv();
   combine(1);
}

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

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

   return 0;
}