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

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

int n;
long long A, B;
long long posib[100010];
long long nrpos;
long long prim[100010];
long long nrp;
long long conf[21];
long long prod, ans;
bool ciur[1000010];

void descompune(long long x) {
    nrp = 0;
    for (long long j = 1; j<=nrpos && posib[j]*posib[j]<=x; j++) {
        bool ok = 0;
        while (x%posib[j] == 0) {
            x /= posib[j];
            ok = 1;
        }
        if (ok) prim[++nrp] = posib[j];
    }
    if (x > 1) {
        prim[++nrp] = x;
    }
    
    //for (int i = 1; i<=nrp; i++) cout << prim[i] << " ";
}

void bkt(long long poz) {
    
    if (poz > nrp) {
        return;
    }
    
    for (long long 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];
    }
}

void faciur() {
    ciur[0] = ciur[1] = 1;
    for (long long i = 2; i*i<=1000000; i++) {
        if (ciur[i] == 0) {
            posib[++nrpos] = i;
            for (long long j = i*i; j<=1000000; j+=i) {
                ciur[j] = 1;
            }
        }
    }
    
}

int main() {
    
    faciur();
    
    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;
}