#include<fstream>
#include<vector>

#define MAXN 2000005

using namespace std;
typedef int64_t var;

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

bool CIUR[MAXN];
var FACT[MAXN];
vector<var> PRIME;

void gen(var m) {
    for(var i=2; i<=m; i++) {
        if(!CIUR[i]) {
            PRIME.push_back(i);
            for(var j=2*i; j<=m; j+=i) {
                CIUR[j] = 1;
            }
        }
    }
}

var aflanr(var cod, var nrf, var a) {
    var t = 1, semn = 0;
    for(var i=0; i<nrf; i++) {
        if(cod & (1 << i)) {
            t*=FACT[i+1];
            semn ^= 1;
        }
    }
    if(semn) return a/t;
    else return -a/t;
}

int main() {
    var n, a, b;
    fin>>n;
    gen(2000001);
    while(n--) {
        fin>>a>>b;
        var nrf = 0, sum = 0;
        if(!CIUR[b]) {
            fout << (a - a/b) << '\n';
            continue;
        }
        for(var i=0; PRIME[i] < b; i++) {
            if(b%PRIME[i] == 0) //DACA B SE DIVIDE CU Pi
                FACT[++nrf] = PRIME[i]; //FACTORUL LUI Pi SE ACTUALIZEAZA IN FACT
        }

        for(var cod=1; cod < 1<<nrf; cod++) {
            sum += aflanr(cod, nrf, a);
        }
        fout << a - sum << '\n';
        continue;
    }
    return 0;
}