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

ifstream cin("pinex.in");
ofstream cout("pinex.out");
#define m 1000005
bitset <m> b;
int k,v[1000000],t;
long long a,c,suma;

void ciur(){
    for(int i=2; i*i<m; i++)
      if(b[i]==0){
        for(int j=i+i; j<m; j+=i)
          b[j]=1;
      }
}
int main(){
    long long div;
    cin>>t;
    for(;t--;){
    cin>>a>>c;
    suma=0; div=1,k=0;
    ciur();
    for(int i=2; i<=c; i++)
      if(b[i]==0)
        if(c%i==0){
           v[++k]=i;
           div*=i;
        }
    for(int i=1; i<=k; i++)
      suma+=a/v[i];
      if(k==1)
        suma-=a/v[1];
      else
      for(int i=1; i<=k; i++)
        for(int j=i+1; j<=k; j++){
          suma-=a/(v[i]*v[j]);
          cout<<suma<<'\n';
        }
    if(div>2)
    suma+=a/div;
    cout<<a-suma<<'\n';
    }
  return 0;
}
// suma=10+6-3+3