#include <bits/stdc++.h>

using namespace std;

const int V_MAX = 1e6;
using i64 = long long;

bool is_prime[V_MAX + 5];
vector<int> primes;

void generate_primes() {
    for(int i = 2; i <= V_MAX; i++) {
        is_prime[i] = true;
    }    
    for(int i = 2; i <= V_MAX; i++) {
        if(is_prime[i]) {
            for(int j = 2 * i; j <= V_MAX; j += i) {
                is_prime[j] = false;
            }
            primes.push_back(i);
        }
    }
}

vector<i64> get_primes(i64 B) {
    vector<i64> ret;
    int d = 0;
    while(d < primes.size() && primes[d] * primes[d] <= B) {
        if(B % primes[d] == 0) {
            ret.push_back(primes[d]);
            while(B % primes[d] == 0) {
                B /= primes[d];
            }
        }
        d++;
    }
    if(B != 1) {
        ret.push_back(B);
    }
    return ret;
}

i64 query(i64 A, i64 B) { ///returneaza cate numere prime cu B sunt <= A.
    vector<i64> primes = get_primes(B);
    int k = primes.size();
    i64 ret = 0;
    for(int conf = 0; conf < (1 << k); conf++) { ///trec prin toate submultimile posibile de factori primi
        i64 product = 1;
        int cnt = 0;
        for(int i = 0; i < k; i++) {
            if(conf & (1 << i)) {
                product *= primes[i];
                cnt++;
            }
        }
        if(cnt % 2 == 0) {
            ret += A / product;
        }
        else {
            ret -= A / product;
        }
    }
    return ret;
}

int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    generate_primes();
    
    int M;
    cin >> M;
    while(M--) {
        i64 A, B;
        cin >> A >> B;
        cout << query(A, B) << "\n";        
    }
    return 0;
}