#include <cstdio>
#include <cmath>
#include <vector>
#define ll long long
using namespace std;

const int MAXCIUR = 1000000;
ll sum = 0;
ll a, b;
vector<bool> ciur;
vector<int> factoriPrimi;
vector<int> stiva;

void find() {
    int limit = MAXCIUR;
//    printf("factori primi ai lui %lld:", b);
    for (int i = 2; i <= limit; ++i) {
        if (ciur[i] && b % i == 0) {
            factoriPrimi.push_back(i);
            printf("%d ", i);
        }
        if (i > b)
            break;
    }
//    printf("\n");
}

void calculCiur() {
    ciur.resize(MAXCIUR + 5, 1);
    int k = sqrt(MAXCIUR);
    for (int i = 2; i <= k; ++i)
        if (ciur[i])
            for (int j = i * i; j <= MAXCIUR; j += i)
                ciur[j] = 0;
}

void addToSum() {
    ll prod = 1;
    for (vector<int>::iterator i = stiva.begin(); i < stiva.end(); ++i) {
//        printf("%d ", *i);
        prod *= *i;
    }
    if (stiva.size() % 2)
        sum += a / prod;
    else
        sum -= a / prod;
//    printf("\nprod=%lld\n",prod);
}

void back() {
    int p = factoriPrimi.size();
    int l;
//    printf("%d\n", p);
    for (int i = 0; i < p; ++i) {
        stiva.push_back(factoriPrimi[i]);
        l = stiva.size();
        if (l > 1 && stiva[l-2] >= stiva[l-1]) {
//            printf("before\n");
            stiva.pop_back();
            continue;
        }
//        printf("after\n");
        addToSum();
        if (l < p)
            back();
        stiva.pop_back();
    }
}

int main() {
    calculCiur();
    int m;
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    scanf("%d", &m);
    for (; m; --m) {
        scanf("%lld%lld", &a, &b);
        sum = 0;
        find();
        back();
        printf("%lld\n", a - sum);
        factoriPrimi.clear();
    }
}