#include <cstdio>
#include <cmath>
#include <vector>

using namespace std;

vector <long long> f;
vector <int> div;
bool c[1000005];

void ciur() {
    c[1] = c[0] = 1;
    for(int i = 4; i <= 1000000; i += 2) {
        c[i] = 1;
    }
    for(int i = 3; i <= 1000; i += 2) {
        if(!c[i])
            for(int j = i * i; j <= 1000000; j += (i << 1))
                c[j] = 1;
    }
    div.push_back(2);
    for(int i = 3; i <= 1000000; i += 2) {
        if(!c[i])
            div.push_back(i);
    }
}

void descompunere(long long n) {
    int e;
    long long d = 0;
    while((long long) div[d] * div[d] <= n && n > 1) {
        e = 0;
        while(n % div[d] == 0) {
            n /= div[d];
            ++ e;
        }
        if(e != 0) {
            f.push_back(div[d]);
        }
        ++ d;
    }
    if(n > 1) {
        f.push_back(n);
    }
}

void solve(long long a, long long b) {
    f.clear();
    descompunere(b);
    long long n, cate, prod, nr, rasp = 0;
    nr = f.size();
    n = 1 << nr;
    for(long long i = 1; i < n; ++ i) {
        cate = 0;
        prod = 1;
        for(long long j = 0; j < nr; ++ j) {
            if(i & (1LL << j)) {
                ++ cate;
                prod *= f[j];
            }
        }
        if(cate & 1) {
            rasp += a / prod;
        } else {
            rasp -= a / prod;
        }
    }
    printf("%lld\n", a - rasp);
}

int main() {
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);

    int t;
    long long a, b;
    ciur();
    scanf("%d", &t);

    for(int i = 1; i <= t; ++ i) {
        scanf("%lld%lld", &a ,&b);
        solve(a, b);
    }

    return 0;
}