#include <iostream>
#include <fstream>
#define int long long

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

const int MAX=1e6;
int t,a,b,i,j,p[100005],n,k,sol,v[MAX+5],g[MAX+5],h[30],cnt;
bool ciur[MAX+5];


int getreunion(int g[], int n)
{
    int r=1;

    for (int i=1; i<=n; i++)
    {
        if (r>a/g[i])
            return 0;
        r*=g[i];
    }
    return a/r;
}

void getdivisors(int x)
{
    int d=1,pt;

    while (p[d]*p[d]<=x && d<=n)
    {
        pt=0;

        while (x%p[d]==0)
        {
            pt++;
            x/=p[d];
        }

        if (pt!=0)
            v[++k]=p[d];

        d++;
    }

    if (x>1)
        v[++k]=x;
}

void cr()
{
    ciur[0]=1; ciur[1]=1;
    for (i=1; i*i<=MAX; i++)
        if (!ciur[i])
            for (j=i*i; j<=MAX; j=j+i)
                ciur[j]=1;

    for (i=2; i<=MAX; i++)
        if (!ciur[i])
            p[++n]=i;
}


void task()
{
    cnt=0;
    for (int i=1; i<=k; i++)
        if (h[i]==1)
            g[++cnt]=v[i];

    if (cnt==0)
        return;

    if (cnt%2==1)
        sol-=getreunion(g,cnt);
    else
        sol+=getreunion(g,cnt);
}

void bkt(int pas)
{
    for (int i=0; i<=1; i++)
    {
        h[pas]=i;

        if (pas<k)
            bkt(pas+1);
        else
            task();
    }
}

signed main()
{
    cr();
    fin>>t;

    while (t)
    {
        fin>>a>>b;

        k=0; sol=a;

        getdivisors(b);

        bkt(1);

        fout<<sol<<"\n";
        t--;
    }
    return 0;
}