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

ifstream cin("pinex.in");
ofstream cout("pinex.out");
#define m 10000005
bitset <m> b;
int k,v[10000005],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];

    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;
}