#include <fstream>
#include <vector>

using namespace std;
typedef int64_t var;

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

vector<var> DIV;
vector<var> PRIME;

vector<bool> PRIM(10000000);
void ciur(var maxx) {
    for(var i=2; i<=maxx; i++) {
        if(!PRIM[i]) {
            PRIME.push_back(i);
            for(var j=i+i; j<=maxx; j+=i) {
                PRIM[j] = 1;
            }
        }
    }
}

void getPrime(var n) {
    DIV.clear();
    for(var d=0; PRIME[d]*PRIME[d] <= n; d++) {
        if(n%PRIME[d] == 0) {
            DIV.push_back(PRIME[d]);
            while(n%PRIME[d] == 0) {
                n /= PRIME[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;
    ciur(1000001);
    fin>>m;
    while(m--) {
        fin>>a>>b;
        getPrime(b);
        fout << checkall(a) << "\n";
    }
}