#include <fstream>
#include <vector>

using namespace std;
typedef int64_t var;

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

vector<var> DIV;

void getPrime(var n) {
    DIV.clear();
    for(var d=2; d*d <= n; d++) {
        if(n%d == 0) {
            DIV.push_back(d);
            while(n%d == 0) {
                n /= d;
            }
        }
    }
    if(n > 1) {
        DIV.push_back(n);
    }
}

var checkall(var t) {
    var nrdiv = DIV.size();
    var total = 0;
    var alp, prod;
    for(var conf = 1; conf < (1 << nrdiv); conf++) {
        alp = -1;
        prod = 1;
        for(var i=0; i<nrdiv; i++) {
            if(conf & (1 << i)) {
                alp *= -1;
                prod *= DIV[i];
            }
        }
        total += alp * t / prod;
    }
    return t - total;
}

int main() {
    var a, b, m;
    fin>>m;
    while(m--) {
        fin>>a>>b;
        getPrime(b);
        fout << checkall(a) << "\n";
    }
}