#include <fstream>
#include <cmath>
#include <algorithm>
#include <cstring>

using namespace std;

#define FOR(i,a,b) for(int i = a; i<=b;i++)
#define MAX_P 1000000

long long int M, A, B, fact[30];
int fprim[80000];
bool prim[MAX_P];

void Ciur()
{
    fill(prim + 2, prim + MAX_P, 1);

    FOR(i,2,MAX_P-1)
        if (prim[i])
        {
            for (int j = 2 * i; j < MAX_P; j += i)
                prim[j] = false;
            fprim[++fprim[0]] = i;
        }
}

long long int Rezolva()
{
    long long int 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 int sol = A;
    for (int i = 1; i < (1 << t); i++)
    {
        long long int 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;
    }

    return sol;
}

int main() {

    ifstream fin("pinex.in");
    ofstream fout("pinex.out");

    Ciur();
    fin>>M;

    FOR(i,1,M)
    {
        fin>>A>>B;
        fout<<Rezolva()<<'\n';
    }
    return 0;
}