#include <fstream>
#include <vector>
using namespace std;
using LL = long long;
LL res;


void solve(LL A, LL B)
{
    vector<LL> prime_facs;
    prime_facs.reserve(20);

    for (LL prime_fac = 2; prime_fac * prime_fac <= B; prime_fac += 1 + prime_fac != 2)
    {
        if (B % prime_fac == 0)
        {
            prime_facs.emplace_back(prime_fac);

            while (B % prime_fac == 0)
            {
                B /= prime_fac;
            }
        }
    }
    if (B > 1)
    {
        prime_facs.emplace_back(B);
    }

    LL nr_subsets = 0, cur_product = 1;
    for (LL i = 1; i < (1LL << prime_facs.size()); ++i)
    {
        for (LL j = 0; j < prime_facs.size(); ++j)
        {
            if ((1LL << j) & i)
            {
                cur_product *= prime_facs[j];
                ++nr_subsets;
            }
        }

        LL sign;
        if (nr_subsets % 2 == 0)
        {
            sign = -1;
        }
        else
        {
            sign = 1;
        }

        res += sign * A / cur_product;

        cur_product = 1;
        nr_subsets = 0;
    }
}


int main()
{
    ifstream fin("pinex.in");

    LL M;
    fin >> M;

    ofstream fout("pinex.out");
    while (M--)
    {
        LL A, B;

        fin >> A >> B;
        solve(A, B);

        fout << A - res << "\n";
        res = 0;
    }
}