#include <fstream>
#include <vector>

using namespace std;

ifstream cin("pinex.in");
ofstream cout("pinex.out");

const int PMAX = 1e6;
long long m, a, b;
long long sol;
bool ciur[PMAX + 2];
vector<int> primes, ans;

void ciurulet() {
    primes.push_back(2);
    for(int i = 3; i  <= PMAX; i += 2) {
        if(!ciur[i]) {
            primes.push_back(i);
            for(long long j = 1LL * i * i; j <= PMAX; j += 2 * i)
                ciur[j] = true;
        }
    }
}

void pinex() {
    sol = 0;
    for(int i = 1; i < (1 << ans.size()); ++i) {
        long long buff = 1;
        int semn = 0;
        for(int j = 0; j < ans.size(); ++j) {
            if((1 << j) & i) {
                ++semn;
                buff *= ans[j];
            }
        }
        if(semn % 2 == 0)
            sol -= a / buff;
        else
            sol += a / buff;
    }
}

void descompunere() {
    for(auto it: primes) {
        if(b % it == 0) {
            ans.push_back(it);
            while (b % it == 0)
                b /= it;
        }
    }
    if(b > 1)
        ans.push_back(b);
}

int main() {
    
    ciurulet();
    cin >> m;
    for(; m; --m) {
        cin >> a >> b;
        descompunere();
        pinex();
        cout << a - sol << "\n";
        ans.clear();
    }
    return 0;
}