#include <bits/stdc++.h>

using namespace std;

const int MAXSQRTB = 1e6;

int M;
long long A, B;

inline int sqrt1(long long nr)  {
    int r = 0, pas = 1 << 20;
    while(pas)  {
        if(1LL * (r + pas) * (r + pas) <= nr)
            r += pas;
        pas >>= 1;
    }
    return r;
}

bool ciur[MAXSQRTB + 5];
vector <int> prim;

inline void do1()  {
    vector <int> div;
    int curr = 0, sqrtb = sqrt1(B);
    long long ans = 0LL;
    while(prim[curr] <= sqrtb && B > 1)  {
        if(B % prim[curr] == 0)  {
            div.push_back(prim[curr]);
            while(B % prim[curr] == 0)
                B /= prim[curr];
        }
        curr++;
    }
    if(B > 1)
        div.push_back(B);
    int nrdiv = div.size();
    long long divi;
    for(int i = 1;i < (1 << nrdiv);i++)  {
        divi = 1LL;
        int hm = 0;
        for(int j = 0;j < nrdiv;j++)  {
            if(i & (1 << j))  {
                divi *= 1LL * div[j];
                hm++;
            }
        }
        if(hm & 1)  {
            ans += 1LL * A / divi;
        }
        else
            ans -= 1LL * A / divi;
    }
    printf("%lld\n", A - ans);
}

int main()  {
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    scanf("%d", &M);
    ciur[1] = 1;
    for(int i = 2;i <= MAXSQRTB;i++)
        if(ciur[i] == 0)  {
            prim.push_back(i);
            for(long long j = 1LL * i * i;j <= MAXSQRTB;j += i)
                ciur[j] = 1;
        }
    for(int i = 1;i <= M;i++)  {
        scanf("%lld%lld", &A, &B);
        do1();
    }
    return 0;
}