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

long long v[50];

int main()
{
    FILE *fi=fopen("pinex.in", "r"), *fo=fopen("pinex.out", "w");
    int m, a, b, div, j, i, n, nrb, y, val, rez;
    fscanf(fi, "%d", &m);
    for(i=0;i<m;i++){
        fscanf(fi, "%lld%lld", &a, &b);
        div=2;
        j=0;
        while(div*div<=b){
            if(b%div==0){
                while(b%div==0)
                    b/=div;
                v[j]=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;
}