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

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

//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];

    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/div;
    cout<<a-suma<<'\n';
    }
  return 0;
}