#include <iostream>
#include <fstream>

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

long long a, b, sub, op[100];
long long n, i, S, j, nr, k, m, p[80000], d[100], nrd, nrp=78498;
bool ciur[1000010];


void suma (long long p)
{
    if (p == k+1)
    {
        long long pF = 1;
        for (int j = 1; j <= k; j++)
            pF *= d[op[j]];
        sub += a/pF;
    }
    else
    {
        for (long long i = op[p-1]+1; i <= nrd; i++)
        {
            op[p] = i;
            suma(p+1);
        }
    }
}

int main ()
{

    for (i = 2; i <= 1000000; i++)
        if (ciur[i] == 0)
        {
            nr++;
            p[nr] = i;
            for (j = 2; j*i <= 1000000; j++)
                ciur[i*j] = 1;
        }

    fin >> m;
    for(int l=1; l<=m; l++)
    {
        fin >> a >> b;
        nrd = 0;
        for (nr=1; b > 1 && nr <= nrp; nr++)
        {
            k = 0;
            while (b%p[nr] == 0)
            {
                b /= p[nr];
                k = 1;
            }
            if (k == 1)
            {
                nrd++;
                d[nrd] = p[nr];
            }
        }
        if (b > 1)
        {
            nrd++;
            d[nrd] = b;
        }

        S = a;
        bool p = 0;
        for (i = 1; i <= nrd; i++)
        {
            k = i;
            sub = 0;
            suma(1);
            if (p == 0)
            {
                S -= sub;
                p = 1;
            }
            else
            {
                S += sub;
                p = 0;
            }
        }
        fout << S << "\n";
    }
}