#include <stdio.h>

using namespace std;

#define NRDMAX 12

int divprim[NRDMAX];

int main()
{
    FILE *fin, *fout;
    fin = fopen("pinex.in", "r");
    fout = fopen("pinex.out", "w");

    int m, i, cnt, d, e, nrd, j, bit, nrdiv;
    long long a, b, p;

    fscanf(fin, "%d", &m);

    for(i = 0; i < m; i++){
        fscanf(fin, "%lld%lld", &a, &b);
        nrd = 0;
        d = 2;
        while(d * d <= b){
            e = 0;
            while(b % d == 0){
                b /= d;
                e++;
            }
            if(e > 0){
                divprim[nrd++] = d;
            }
            d++;
        }
        if(b > 1){
            divprim[nrd++] = b;
        }
        cnt = 0;
        for(j = 1; j < (1LL << nrd); j++){
            p = 1;
            nrdiv = 0;
            for(bit = 0; bit < nrd; bit++){
                if(j & (1 << bit)){
                    p *= divprim[bit];
                    nrdiv++;
                }
            }
            if(nrdiv & 1){
                cnt += a / p;
            }
            else{
                cnt -= a / p;
            }
        }
        fprintf(fout, "%lld\n", a - cnt);
    }

    fclose(fin);
    fclose(fout);
    return 0;
}