#include <fstream>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
long long m, A, B, k, d[10001];
void calcul(int x)
{ int nr, i;
    k=0;
    i=2;
    while (x>1)
    { nr=0;
      while (x%i==0)
      { nr++;
        x=x/i;
      }
      if (nr) d[++k]=i;
      i++;
    }
}
int main()
{
    f>>m;
    for (int z=1;z<=m;z++)
    { f>>A>>B;
      calcul(B);
      int nr=0;
      for (int i=1;i<(1<<k);i++)
      { int s=0;
        int p=1;
        for (int j=0;j<k;j++)
            if (i&(1<<j))
            { s++;
              p=p*d[j+1];
            }
        if (s&1) nr=nr+A/p;
        else nr=nr-A/p;
      }
      g<<A-nr<<'\n';
    }
    g<<'\n';
    return 0;
}