#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

const int maxc = 1e6+5;
typedef long long lint;

int vp[maxc / 10], k;
bool pr[maxc];
int v[100];

void eratostene() {
    int i, j;
    vp[++k] = 2;
    for(i = 3; i <= maxc - 5; i += 2) {
        if(pr[i] == 0) {
            vp[++k] = i;
            for(j = i * 3; j <= maxc - 5; j += (i << 1)) {
                pr[j] = 1;
            }
        }

    }
}

lint solve(lint a, lint b) {
    lint d = 1;
    int vk = 0;
    memset(v, 0, sizeof(v));
    while(b != 1 && d < k) {
        if(b % vp[d] == 0) {
            v[++vk] = vp[d];
            while(b % vp[d] == 0) { b /= vp[d]; }
        }
        if(vp[d] * vp[d] > b && b != 1) {
            v[++vk] = b; b = 1;
        }
        ++d;
    }
    if(b != 1) { v[++vk] = b; }
    lint i, j, nr = 0, prod = 1, neg = 1, ans = 0;
    for(i = 1; i <= (1LL << vk) - 1; i ++) {
        nr = 0; prod = 1; neg = 1;
        for(j = 1; j <= vk; j ++) {
            if((i & (1LL << (j-1))) != 0) {
                prod *= v[j];
                ++ nr;
            }
        }
        if(nr % 2 == 0) { neg = -1; }
        ans += neg * a / prod;
    }
    return a - ans;
}

int main()
{
    int q;
    lint a, b;
    eratostene();
    f >> q;
    while(q --) {
        f >> a >> b;
        g << solve(a, b) << '\n';
    }

    f.close(); g.close();
    return 0;
}