#include <iostream>
#include<fstream>
#include<vector>
using namespace std;ifstream fin("pinex.in");ofstream fout("pinex.out");
int m,erat[1000001],i,j,cnt,k;long long a,b,p,rez;bool ok;vector<int>prim,v;vector<int>::iterator it;
int main()
{
    for(i=2;i<=1e6;i++)if(!erat[i]){
            prim.push_back(i);
        for(j=i*2;j<=1e6;j+=i)erat[j]=1;
    }
    fin>>m;while(m--){rez=0;
        fin>>a>>b;v.clear();
        for(it=prim.begin();it!=prim.end()&&(*it)*(*it)<=b;it++){
            ok=0;while(b%*it==0){ok=1;b/=*it;}
            if(ok)v.push_back(*it);
        }if(b>1)v.push_back(b);k=v.size();
        for(i=1;i<(1ll<<k);i++){
            cnt=0;p=1;for(j=0;j<k;j++)if(i&(1ll<<j)){if(p>a/v[j]){p=a+1;break;}p*=v[j];cnt++;}
            if(cnt&1)rez+=a/p;
            else rez-=a/p;
        }fout<<a-rez<<'\n';
    }
    return 0;
}