#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

vector<long long> gasesteDivizorii(long long b) {
    vector<long long> divizori;
    for (long long i = 1; i * i <= b; i++)
        if (b % i == 0) {
            divizori.push_back(i);
            if (i != b / i)
                divizori.push_back(b / i);
        }
    return divizori;
}

int mobius(long long n) {
    if (n == 1) return 1;
    int p = 0;
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            n /= i;
            if (n % i == 0) return 0;
            p++;
        }
    }
    if (n > 1) p++;
    return (p % 2 == 0) ? 1 : -1;
}

// Functia principala
int main() {
    ifstream fin("pinex.in");
    ofstream fout("pinex.out");
    
    int m;
    fin >> m;
    
    for (int i = 0; i < m; i++) {
        long long a, b;
        fin >> a >> b;
        
        vector<long long> divizori = gasesteDivizorii(b);
        long long rezultat = 0;
        
        for (auto d : divizori)
            rezultat += mobius(d) * (a / d);
        
        fout << rezultat << '\n';
    }
        
    return 0;
}