#include<fstream>
#define NR_MAX 1000001
using namespace std;

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

int T;
long long A,B;
char V[1<<17];
int fact[40];
int P[80000]={0,2},K=1;
inline void ciur()
{
    int i2;
    for(int i=3;i<NR_MAX;i+=2)
    {
        if(V[i>>4] & (1<<((i>>1)&7)))
            continue;
        P[++K]=i;
        for(int j=i+(i2=i+i);j<NR_MAX;j+=i2)
            V[j>>4]|=1<<((j>>1)&7);
    }



}

void solve()
{
    long long t=0,d=0;
    while(B>1)
    {
        if( !(B%P[++d]) )
        {
            fact[++t]=P[d];
            while( !(B%P[d]) )
                B/=P[d];
        }
        if(1LL*P[d]*P[d]>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;
    }
    out<<sol<<'\n';
}

int main()
{
    ciur();
    for(in>>T;T;T--)
    {
        in>>A>>B;
        solve();
    }


    return 0;
}