#include <bits/stdc++.h>
#define maxim 1000005

using namespace std;

ifstream f ("pinex.in");
ofstream g("pinex.out");

bool ciur[maxim];
vector < int >  prime;
vector < int > divizor;
int ans[200];
long long m,a,b;
long long fin=0;

void era()
{
    prime.push_back(2);
    int i;
    for (i=3 ; i*i <= maxim; i+=2)
        if (ciur[i]==0)
        {

            prime.push_back(i);
            for (int j = i * i; j <= maxim; j += 2 * i)
                ciur[j] = 1;
        }
    for (; i<=maxim ; i+=2)
        if (ciur[i]==0)
            prime.push_back(i);

}


void submultimi(int k )
{
  if (k==divizor.size()+1)
      return;
  for (int i=ans[k-1]+1; i<=divizor.size();i++)
  {
      ans[k]=i;
      long long pr=1;
      int semn=-1;
      if (k&1)
          semn=1;
      for (int j=1 ;j <= k ;j++)
          //cout<<divizor[ans[j]-1]<<" ";
          //cout<<ans[j]<<" ";
          // cout<<endl;
          pr=1LL*pr*divizor[ans[j]-1];
      fin=fin+1LL*semn*a/pr;
      submultimi(k+1);
  }

}


void rez()
{
    divizor.clear();
    ans[0]=0;
    int d=0;
    while ( d<= prime.size() && 1LL*prime[d]*prime[d] <= b )
    {
        if (b%prime[d]==0) {
            divizor.push_back(prime[d]);
            while (b % prime[d] == 0)
                b /= prime[d];
        }
        d++;
    }
    if (b!=1)
        divizor.push_back(b);
   // cout<<divizor.size();
    submultimi(1);

}

int main()
{
    f>>m;
    era();
    while (m--)
    {
        fin=0;
        f>>a>>b;
        rez();
        g<<a-fin<<'\n';
    }


}