#include <stdio.h>
#include <vector>

const int maxb = 1000000;
int i, j;
bool prime[maxb + 2];
std::vector<int> divizori, nrprime;

void ciur(int nrmax)
{
    for(i = 2;i * i <= nrmax;prime[i++] = true);

    for(i = 2;i * i <= nrmax;(i==2) ? i++ : i+=2)
    {
        if(prime[i])
        {
            for(j = i * 2;j * j <= nrmax;j+=i) prime[j] = false;
            nrprime.push_back(i);
        }
    }
}

void finddiv(int n)
{
    int d, nr = n;
    bool gasitdiv;

    for(i = 0;i < (signed)nrprime.size();i++)
    {
        d = nrprime[i]; gasitdiv = 0;

        if(d * d >= nr)
        {
            if(n > 1) divizori.push_back(n);
            return;
        }

        while(n > 1 and n % d == 0) { n/=d; gasitdiv = 1; }
        if(gasitdiv) divizori.push_back(d);
    }
}

int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);

    int nrq, a, b;

    ciur(maxb);

    scanf("%d", &nrq);

    while(nrq--)
    {
        scanf("%d %d", &a, &b);

        divizori.clear();
        finddiv(b);

        int d;
        long long prod, sol = a;

        for(i = 1;i < (1<<(signed)divizori.size());i++)
        {
            prod = 1;
            d = 0;

            for(j = 0;j < (signed)divizori.size();j++)
                if(i & (1 << j))
                {
                    d++;
                    prod *= divizori[j];
                }

            sol += ((d % 2) ? -1 : 1) * a / prod;
        }

        printf("%lld\n", sol);
    }
}