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

ifstream cin("pinex.in");
ofstream cout("pinex.out");
const int m=1000005;
bitset <m> b;
long long a,c,suma,k,t,di;
int v[10000],x[10000],q;

void ciur(){
    for(int i=2; i*i<=m; ++i)
      if(b[i]==0){
        x[++q]=i;
        for(int j=i+i; j<=m; j+=i)
          b[j]=1;
      }
}
int main(){
    ciur();
    cin>>t;
    for(;t--;){
    cin>>a>>c;
    suma=0; di=1,k=0;
    for(int i=1; i<=q; ++i)
        if(c%x[i]==0){
           v[++k]=x[i];
           di*=x[i];
        }
    for(int i=1; i<=k; ++i)
      suma+=a/v[i];

    for(int i=1; i<=k; ++i)
        for(int j=i+1; j<=k; ++j){
          suma-=a/(v[i]*v[j]);
        }
    if(k>2)
    suma+=a/di;
    cout<<a-suma<<'\n';
    }
  return 0;
}