#include <fstream>
#include <vector>

using namespace std;

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

// Limita superioara pentru ciurul primelor
const int MAX_PRIME = 1000000;
vector<int> prime;
vector<bool> estePrim(MAX_PRIME + 1, true);

void gasestePrime() {
    for (int i = 2; i <= MAX_PRIME; i++)
        if (estePrim[i]) {
            prime.push_back(i);
            for (long long j = 1LL * i * i; j <= MAX_PRIME; j += i)
                estePrim[j] = false;
        }
}

// Calculeaza valoarea functiei Mobius pentru un numar
int mobius(long long n) {
    int factori = 0;
    for (int i = 0; prime[i] * prime[i] <= n and i < prime.size(); i++) {
        if (n % prime[i] == 0) {
            n /= prime[i];
            if (n % prime[i] == 0) return 0;
            factori++;
        }
    }
    if (n > 1) factori++;
    return factori % 2 == 0 ? 1 : -1;
}

int main() {
    int numarIntrebari;
    fin >> numarIntrebari;
    gasestePrime();

    for (int i = 0; i < numarIntrebari; i++) {
        long long a, b;
        fin >> a >> b;
        
        vector<long long> divizori = gasesteDivizorii(b);
        long long rezultat = 0;
        
        for (long long d : divizori) {
            int mu = mobius(d);
            if (mu != 0)
                rezultat += mu * (a / d);
        }
        
        fout << rezultat << '\n';
    }
    
    fin.close();
    fout.close();
    
    return 0;
}