#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
vector<int> szita_fuggyveny()
{
vector<bool>szita(1e6/2+1,true);
szita[0]=false;
int i=3;
int db=0;
int sz=szita.size();
while((i>>1)<sz)
{
if(szita[i>>1]==true)
{
db++;
int j=i+i+i;
while(j<=sz)
{
szita[j>>1]=false;
j+=i+i;
}
}
i+=2;
}
vector<int>prim(db+1);
prim[0]=2;
int j=1;
for(int i=3;(i>>1)<sz;i+=2)
if(szita[i>>1])
prim[j++]=i;
return prim;
}
vector<long long> prim_teny(long long b,const vector<int>&prim)
{
int i=0;
vector<long long>v;
long long x=prim.size();
while(b>1 && i<x)
{
int d=prim[i];
if(b%d==0){
while(b%d==0)
{
b/=d;
}
v.push_back(d);
}
i++;
}
if(b>1)
v.push_back(b);
return v;
}
long long solve(long long a,long long b,const vector<int>&prim)
{
auto v=prim_teny(b,prim);
long long db=0;
int sizev=v.size();
for(size_t i=1;i<(1<<sizev);i++)
{
int cnt=0;
long long prod=1;
for(int j=0;j<sizev;j++)
if((1ll<<j)&i){
++cnt;
prod*=v[j];
}
if(cnt%2)db+=a/prod;
else db-=a/prod;
}
return a-db;
}
int main()
{
ifstream be("pinex.in");
ofstream ki("pinex.out");
int n;
be>>n;
auto prim=szita_fuggyveny();
for(int i=0;i<n;i++)
{
long long a,b;
be>>a>>b;
ki<<solve(a,b,prim)<<endl;
}
return 0;
}