#include <fstream>
#include <vector>

using namespace std;

ifstream in("pinex.in");
ofstream out("pinex.out");
long long q, a, b;
int prime[200005];
int k;
bool ciur[1000005];
vector<int> fact;
long long ans, sum, rez;
int x[105];

void build_ciur()
{
    ciur[0] = ciur[1] = 1;

    for(int i = 2; i<=1000000; i++)
    {
        if(ciur[i] == 0)
        {
            k++;
            prime[k] = i;

            for(int j = 2; i*j<1000000; j++)
            {
                ciur[i*j] = 1;
            }
        }
    }
}

void add(int maxim)
{
    long long suma = 0;
    long long prod = 1;

    for(int i = 1; i<=maxim; i++)
    {
        prod *= fact[x[i]];
    }

    suma = a / prod;

    sum += suma;
}

void backt(int poz, int maxim)
{
    for(int i = x[poz-1] + 1; i<fact.size(); i++)
    {
        x[poz] = i;

        if(poz == maxim)
        {
            add(maxim);
        }
        else
        {
            backt(poz + 1, maxim);
        }
    }
}

int main()
{
    build_ciur();

    in>>q;

    while(q--)
    {
        in>>a>>b;
        ans = 0;
        fact.clear();

        fact.push_back(0);

        for(int i = 1; i<=k && prime[i] * prime[i] <= b; i++)
        {
            if(b % prime[i] == 0)
            {
                fact.push_back(prime[i]);
            }

            while(b % prime[i] == 0)
            {
                b /= prime[i];
            }
        }

        if(b > 1)
        {
            fact.push_back(b);
        }

        /*for(auto i: fact)
        {
            out<<i<<" ";
        }
        out<<'\n';*/

        for(int i = 1; i<fact.size(); i++)
        {
            sum = 0;

            backt(1, i);

            //out<<sum<<" ";

            if(i % 2 == 1)
            {
                ans += sum;
            }
            else
            {
                ans -= sum;
            }
        }

        rez = a - ans;
        //out<<" -> "<<ans<<" -> ";

        out<<rez<<'\n';
    }

    return 0;
}