#include <fstream>
#include <cmath>
#include <cstdlib>
#include<iostream>
using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

int n, A, B;
int prim[21], nrp;
int conf[21];
int prod, ans;

void descompune(int x) {
    nrp = 0;
    int nr = 2;
    while (x > 1) {
        bool ok = 0;
        while (x > 1 && x%nr == 0) {
            x /= nr;
            ok = 1;
        }
        if (ok) {
            prim[++nrp] = nr;
        }
        nr++;
    }
}

void bkt(int poz) {
    
    if (poz > nrp) {
        return;
    }
    
    for (int i = conf[poz-1]+1; i<=nrp; i++) {
        conf[poz] = i;
        prod *= prim[i];
        if (poz%2 == 1) {
            ans += (A/prod);
        } else {
            ans -= (A/prod);
        }
        
        bkt(poz+1);
        prod /= prim[i];
    }
}

int main() {
    
    fin >> n;
    for (int t = 1; t<=n; t++) {
        fin >> A >> B;
        descompune(B);
        prod = 1;
        ans = 0;
        bkt(1);
        fout << A - ans << "\n";
    }
    
    return 0;
}