#include <stdio.h>
#include <stdlib.h>

long long v[50];
char ciur[1000000];
int prime[80000];

int ciurul(){
  int i, j;
  ciur[0]=ciur[1]=1;
  for(i=2;i*i<1000000;i++)
    if(ciur[i]==0)
      for(j=i*i;j<1000000;j+=i)
        ciur[j]=1;
  j=0;
  for(i=2;i<1000000;i++)
    if(ciur[i]==0){
      prime[j]=i;
      j++;
    }
  return j;
}

int main()
{
    FILE *fi=fopen("pinex.in", "r"), *fo=fopen("pinex.out", "w");
    long long a, b, div, n, val, rez;
    int i, j, m, nrb, y, np;
    np=ciurul();
    fscanf(fi, "%d", &m);
    for(i=0;i<m;i++){
        fscanf(fi, "%lld%lld", &a, &b);
        div=0;
        j=0;
        while(prime[div]*prime[div]<=b && div<np){
            if(b%prime[div]==0){
                while(b%prime[div]==0)
                  b/=prime[div];
                v[j]=prime[div];
                j++;
            }
            div++;
        }
        if(b!=1){
            v[j]=b;
            j++;
        }
        n=j;
        rez=0;
        for(j=1;j<(1<<n);j++){
            nrb=0;
            val=1;
            for(y=0;y<n;y++)
                if(j&(1<<y)){
                    val*=v[y];
                    nrb++;
                }
            if(nrb%2==0)
                rez-=a/val;
            else
                rez+=a/val;
        }
        fprintf(fo, "%lld\n", a-rez);
    }
    return 0;
}