#include <bits/stdc++.h>
#define N 1000002

using namespace std;

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

int m;
unsigned long long a, b, ans;
bool ciur[N];
vector <unsigned long long> prim;
unsigned long long divPrim[1000];

void Ciur()
{
    ciur[0] = ciur[1] = 1;
    for (int i = 4; i < N; i += 2)
        ciur[i] = 1;

    for (int i = 3; i * i < N; i += 2)
        if (!ciur[i])
            for (int j = i * i; j < N; j += 2 * i)
            ciur[j] = 1;

    prim.push_back(0);
    for (int i = 1; i < N - 1; i++)
        if (!ciur[i])
            prim.push_back(i);
}

void Solve()
{
    int ind = 1;
    unsigned long long d = prim[1];
    while (b != 1)
    {
        if (b % d == 0)
        {
            while (b % d == 0)
                b /= d;
            divPrim[++divPrim[0]] = d;
        }

        if (d * d <= b)
            d = prim[++ind];
        else
            d = b;
    }

    for (int i = 1; i < (1 << divPrim[0]); i++)
    {
        unsigned long long prod = 1;
        int cnt = 0;

        for (unsigned j = 0; j < divPrim[0]; j++)
            if (i & (1 << j))
            {
                prod *= divPrim[j + 1];
                cnt++;
            }

        if (cnt & 1)
            ans += (a / prod);
        else
            ans -= (a / prod);
    }

    fout << a - ans << "\n";
}

void Reset()
{
    ans = 0;
    divPrim[0] = 0;
}

int main()
{
    Ciur();
    fin >> m;
    while (m--)
    {
        fin >> a >> b;
        Solve();
        Reset();
    }
    return 0;
}