#include <bits/stdc++.h>
using namespace std;

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

vector<long long> divi, nrPrimes;

const int MAXDIV = 1e5;

char ciur[MAXDIV + 1];

long long pinex(long long a){
    long long ans = 0, cnt, i, j;

    for(i = 1; i < (1 << divi.size()); i++){ // Bit Mask-ul
        cnt = 1;
        for(j = 0; j < divi.size(); j++){ // 2 ^ j = bit-ul
            if(i & (1LL << j)){ // Verificam daca este prezent in bit mask-ul curent
                cnt *= divi[j];
            }
        }

        if(__builtin_popcount(i) & 1){
            ans += a / cnt;
        } else {
            ans -= a / cnt;
        }
    }
    return a - ans;
}

int main() {
    long long m, a, b, d, i;

    for(d = 2; d * d <= MAXDIV; d++){
        if(ciur[d] == 0){
            for(i = d * d; i <= MAXDIV; i += d){
                ciur[i] = 1;
            }
        }
    }

    for(d = 2; d <= MAXDIV; d++){
        if(ciur[d] == 0){
            nrPrimes.push_back(d);
        }
    }

    fin >> m;

    while(m--){
        fin >> a >> b;

        divi.clear();

        d = nrPrimes[i = 0];
        while (d * d <= b) {
            if (b % d == 0) {
                do {
                    b /= d;
                } while (b % d == 0);
                divi.push_back(d);
            }
            d = nrPrimes[i++];
        }
        if(b > 1){
            divi.push_back(b);
        }

        fout << pinex(a) << '\n';
    }

    return 0;
}