#include <iostream>
#include <fstream>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");

long long n,m,v[10001],nr,sum,q,pr=1;
bool b[10001];
int ok=1;

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()
{//for(int j=1;j<=nr;j++)if(b[j])g<<v[j]<<" ";g<<endl;
 sum+=m/(pr*ok);//g<<m/pr<<" "<<ok<<endl;
 ok=-ok;


}

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

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

}