#include <iostream>
#include <fstream>

ifstream fin("pinex.in");
ofstream fout("pinex.out");

using namespace std;
long long d[12]; //  d[1].....d[n]
int n;
long long a, b, ans;
int s[12];

bool ciur[1000001];
 int p[200000]; // p[1]=2  p[2]=3 .......p[cnt]<=1 000 000
int cnt;
void calculare() {
  ciur[0] = 1;
  ciur[1] = 1;
  for (int i = 2; i*i <= 1000001; i++)
    if (!ciur[i]) {
      for (int j = i; i * j <= 1000001; j++)
        ciur[ i*j ]=1;
    }
  for (int i = 2; i <= 1000001; i++)
    if (!ciur[i])
      p[++cnt] = i;
}

void produs (int k) {
  long long p = 1;

  for (int i = 1;  i<= k; i++) {
    p *= d[ s[i] ];
  }

  if(k%2==0) ans = ans -  a / p;
  else
    ans += (a / p);
}



void bkt (int k, int nr) {
  for (int i = s[k-1]+1 ; i <= n+k-nr; i++) {
   s[k] = i;

   if (k == nr) {
        produs(k);
   } else
     bkt(k + 1,nr) ;

  }
}

int main()
{
    int m; fin >> m;
    calculare();
    for(int i=1; i<=m; i++)
    {
        fin >> a >> b;
        ans=0;
        n=0;
        for(int j=1; j<=cnt && p[j]*p[j]<=b   ; j++)
          if(b%p[j]==0)
          {
            d[++n]=p[j];

            while(b%p[j]==0)
                b/=p[j];
          }
        if(b>1) { n++;  d[n]=b;}

        for(int j=1; j<=n; j++)
          bkt(1, j);

        fout << a- ans << '\n';
    }

    return 0;
}