#include <fstream>
#include <vector>

using namespace std;

const int VALMAX = 1000000;

bool compus[1 + VALMAX];

vector<int> prime;
vector<int> primeB;

long long sol;

long long a, b;

long long produs;

void ciur()
{
    compus[0] = true;
    compus[1] = true;

    for (int i = 2; i <= VALMAX; i++)
    {
        if (!compus[i])
        {
            prime.emplace_back(i);
            for (long long j = 1ll * i * i; j <= VALMAX; j += i)
                compus[j] = true;
        }
    }
}

void bkt(int index, int nrElemLuate)
{
    if (index == primeB.size())
    {
        if (nrElemLuate != 0)
        {
            if (nrElemLuate % 2 == 1)
                sol += a / produs;
            else
                sol -= a / produs;
        }
        return;
    }

    produs *= primeB[index];
    bkt(index + 1, nrElemLuate + 1);
    produs /= primeB[index];
    bkt(index + 1, nrElemLuate);
}

int main()
{
    ios_base::sync_with_stdio(false);

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

    int m;
    in >> m;

    ciur();

    for (int i = 1; i <= m; i++)
    {
        in >> a >> b;

        primeB.clear();

        for (int i = 0; i < prime.size(); i++)
        {
            if (b % prime[i] == 0)
            {
                while (b % prime[i] == 0)
                    b /= prime[i];

                primeB.emplace_back(prime[i]);
            }
        }

        if (b > 1)
            primeB.emplace_back(b);

        sol = 0;
        produs = 1;

        bkt(0, 0);

        out << a - sol << '\n';
    }

    in.close();
    out.close();

    return 0;
}