#include <fstream>
#include <bitset>
#include <vector>

using namespace std;

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

const int VMAX = 1'000'000;

bitset<VMAX + 1> ciur;
vector<int> prim;

void Precalc()
{
    ciur[0] = ciur[1] = 1;
    for(int i = 4; i <= VMAX; i += 2)
        ciur[i] = 1;
    ///
    for(int i = 3; i * i <= VMAX; i++)
        if(!ciur[i])
            for(int j = i * i; j <= VMAX; j += i << 1)
                ciur[j] = 1;
    ///
    prim.push_back(2);
    for(int i = 3; i <= VMAX; i += 2)
        if (!ciur[i])
            prim.push_back(i);
}

vector<long long> Descomp(long long B)
{
    vector<long long> fact;
    int i = 0;
    while(B > 1)
    {
        if(B % prim[i] == 0)
        {
            fact.push_back(prim[i]);
            while(B % prim[i] == 0)
                B /= prim[i];
        }
        i++;
        if (i >= prim.size() || (long long)prim[i] * prim[i] > B)
            break;
    }
    if(B > 1)
        fact.push_back(B);
    return fact;
}

void Solve()
{
    long long A, B, rez;
    f >> A >> B;
    ///
    vector<long long> fact = Descomp(B);
    int X = (int)fact.size();
    ///
    rez = A;
    for(int i = 1; i < (1 << X); i++)
    {
        long long prod = 1;
        int nr = 0;
        for(int j = 0; j < X; j++)
            if(i & (1 << j))
            {
                prod *= fact[j];
                nr++;
            }
        nr = 1 - ((nr & 1) << 1);
        rez += (long long)nr * (A / prod);
    }
    g << rez << '\n';
}

int main()
{
    Precalc();
    int M;
    f >> M;
    while(M--)
        Solve();
    f.close();
    g.close();
    return 0;
}