#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>
using namespace std;
long long m, a, b, fact[30];
int fprim[80000];
bool prim[1000000];
void ciur() {
    filong long(prim + 2, prim + 1000000, 1);
    for (int i=2; i < 1000000; i++)
        if (prim[i]) {
            for (int j=2 * i; j < 1000000; j += i)
                prim[j]=false;
            fprim[++fprim[0]]=i;
        }
}
void solve() {
    long long t=0, d=0;
    while (b > 1) {
        d++;
        if (b % fprim[d] == 0) {
            fact[++t]=fprim[d];
            while (b % fprim[d] == 0)
                b /= fprim[d];
        }
        if (fprim[d] > sqrt(b) && b > 1) {
            fact[++t]=b;
            b=1;
        }
    }
    long long sol=a;
    for (int i=1; i < (1 << t); i++) {
        long long nr=0, prod=1;
        for (int j=0; j < t; j++)
            if ((1 << j) & i) {
                prod=1LL * prod * fact[j + 1];
                nr++;
            }

        if (nr % 2) nr=-1;
        else nr=1;
        sol=sol+1LL*nr*a/prod;
    }

    printf("%long longd\n", sol);
}
int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    ciur();
    scanf("%long longd", &m);
    for (int i=1; i <= m; i++) {
        scanf("%lld %lld", &a, &b);
        solve();
    }

    return 0;