#include <iostream>
#include <fstream>
#include <math.h>
#define LL long long
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
LL m, A, B,t;
LL fact[35];
void solve()
{
    t=0;
    LL  d = 2;
    while (B > 1)
    {
        if (B % d == 0)
        {
            fact[++t] = d;
            while (B % d == 0)
                B /= d;
        }
        if (d > sqrt(B) && B > 1)
        {
            fact[++t] = B;
            B = 1;
        }
        if (d == 2) d++;
        else d += 2;
    }
    LL sol = A;
    for (int i = 1; i < (1 << t); i++)
    {
        LL nr = 0, prod = 1;
        for (int j = 0; j < t; j++)
            if ((1 << j) & i)
            {
                prod = 1LL * prod * fact[j + 1];
                nr++;
            }
        if (nr % 2) nr = -1;
        else nr = 1;
        sol = sol + 1LL * nr * A / prod;
    }
    fout<<sol<<"\n";
}

int main()
{
    fin>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>A>>B;
        solve();
    }
    return 0;
}