#include <fstream>

using namespace std;

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

#define int long long int

#define MAXFACT 50

int fact[MAXFACT];

int teste,x,y;

void solve (int a, int b);

signed main()
{
    fin>>teste;
    while (teste)
    {
        teste--;
        fin>>x>>y;
        solve(x,y);
    }

    return 0;
}


void solve (int a, int b)
{
    int t=0,d=2,answer=a;
    while (b>1)
    {
        if (b%d==0)
        {
            fact[++t]=d;
            while (b%d==0)
            {
                b/=d;
            }
        }
        if (d*d>b && b>1)
        {
            fact[++t]=b;
            b=1;
        }
        if (d==2)
        {
            d++;
        }
        else
        {
            d+=2;
        }
    }
    for (int i=1; i<(1<<t); i++)
    {
        int nr=0,prod=1;
        for (int j=1; j<=t; j++)
        {
            if ((1<<(j-1))&i)
            {
                prod*=fact[j];
                nr++;
            }
        }
        if (nr%2)
        {
            nr=-1;
        }
        else
        {
            nr=1;
        }
        answer+=nr*a/prod;
    }
    fout<<answer<<'\n';
}