#include <stdio.h>
#include <stdlib.h>
#define maxn 1000000

using namespace std;

bool c[maxn];
long long prim[maxn];
long long di[20];

void ciuruiala(){
    for(int i=2; i*i<=maxn; i++){
        if(!c[i]){
            for(int j=i*i; j<=maxn; j+=i){
                c[j]=1;
            }
        }
    }
    int k=0;
    for(int i=2; i<=maxn; i++){
        if(!c[i]){
            prim[k]=i;
            k++;
        }
    }
}

long long sol(long long a, long long b){
    long long s=0;
    int i,j,k;
    k=0;
    for(i=0; prim[i]*prim[i]<=b; i++){
        if(b%prim[i]==0){
            b/=prim[i];
            di[k]=prim[i];
            k++;
        }
    }
    if(b>1){
        di[k]=b;
        k++;
    }
    for(i=1; i<(1<<k); i++){
        int par=0;
        long long d=1;
        for(j=0; j<k; j++){
            if((i&(1<<j))!=0){
                par=(par^1);
                d=d*di[j];
            }
        }
        s+=((a/d)*(par*2-1));
    }
    return s;
}


int main()
{
    FILE *fin, *fout;
    long long n,a,b;

    ciuruiala();

    fin=fopen("pinex.in","r");
    fout=fopen("pinex.out","w");
    fscanf(fin,"%lld",&n);
    for(n;n>0;n--){
        fscanf(fin,"%lld%lld",&a,&b);
        fprintf(fout,"%lld\n",a-sol(a,b));
    }
    fclose(fin);
    fclose(fout);
    return 0;
}