#include <bits/stdc++.h>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
#define M 1000000
long long m,a,b,fact[30];
int fprim[80000], prim[M];
void prec()
{
    for(int i=2;i<M;i++)
        if(!prim[i])
        {
            for(int j=2*i;j<M;j+=i)
                prim[j]=1;
            fprim[++fprim[0]] = i;
        }
}
void solve()
{
    long long t=0,d=0;
    while(b>1)
    {
        d++;
        if(b%fprim[d]==0)
        {
            fact[++t]=fprim[d];
            while(b%fprim[d]==0)
                b/=fprim[d];
        }
        if(fprim[d]>sqrt(b)&&b>1)
        {
            fact[++t]=b;
            b=1;
        }
    }
    long long sol=a;
    for (int i = 1; i < (1 << t); i++)
    {
        long long 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;
    }
    g<<sol<<"\n";
}
int main()
{
    prec();
    f>>m;
    for(int i=1;i<=m;i++)
    {
        f>>a>>b;
        solve();
    }
}