#include <iostream>
#include <fstream>
using namespace std;

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

long long n,m,v[10001],nr,sum,q;
bool b[10001];

bool prim(int a)
{
 if(a<2)return 0;
 if(a<4)return 1;
 if(!(a&1)||!(a%3))return 0;
 for(int d=5;d*d<=a;d+=6)
    if(!(a%d)||!(a%(d+2)))return 0;
    return 1;
}

void div(int n)
{int i;
 for( i=1;i<=n;i++)if(n%i==0&&prim(i))v[++nr]=i;
}

void afis()
{int ct=0,pr=1;
 for(int j=1;j<=nr;j++)
    if(b[j]){ct++;pr*=v[j];}
    if(ct%2==0)pr=-1*pr;
    sum+=m/pr;
}

void backprod(int k)
{
 for(int i=1;i<=nr;i++)
  if(!b[i]&&i>=k){b[i]=1;
                  afis();
                  backprod(i);
                  b[i]=0;
                 }
}

int main()
{f>>q;
 for(int r=1;r<=q;r++)
 {f>>m>>n;nr=0;sum=0;
  div(n);
  backprod(1);
 g<<m-sum<<'\n';
 }
    return 0;
}