#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[100000];

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(){
    ciur();
    cin>>t;
    for(;t--;){
    cin>>a>>c;
    suma=0; di=1,k=0;
    for(int i=2; i<=c/2; ++i)
      if(b[i]==0)
        if(c%i==0){
           v[++k]=i;
           di*=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;
}