#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

#define ll long long

using namespace std;

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

const int MAX = 1e6 + 10;

ll M, A, B, sol;
vector <bool> C(MAX, 1);
vector <int> D, F;

void Precomp()
{
    for(int i = 2; i <= MAX; i++)
        if(C[i])
        {
            D.push_back(i);
            for(int j = i + i; j <= MAX; j += i)
                C[j] = 0;
        }
}

void Solve()
{
    for(int i = 0; D[i] * D[i] <= B && i < D.size(); i++)
        if(B % D[i] == 0)
        {
            F.push_back(D[i]);
            while(B % D[i] == 0)
                B /= D[i];
        }
    if(B > 1)
        F.push_back(B);

    int N = F.size();
    int confmax = (1 << N);

    sol = 0;
    for(int conf = 1; conf < confmax; conf++)
    {
        ll nr  = 1, n = 0, ok;
        for(int j = 0; j < N; j++)
            if(conf & (1 << j))
            {
                nr *= 1LL * F[j];
                n++;
            }
        if(n % 2) ok = 1;
        else ok = -1;
        sol += 1LL * ok * A / nr;
    }
    fout << (A - sol) << '\n';
    F.clear();
}

int main()
{
    Precomp();
    fin >> M;
    while(M--)
    {
        fin >> A >> B;
        Solve();
    }
    return 0;
}