#include <iostream>
#include <cstdio>
#include <vector>
#define maxp 1000000
#include <cstring>
using namespace std;

int m,k;
long long a,b;
int div[maxp],fprim[80005];
bool prim[maxp],viz[80005];
long long s,p;

void generare()
{
    fill(prim + 2, prim + maxp, 1);

    for (int i=2;i<=maxp;i++)
        {
            if (prim[i]==1)
                {
                    for (int j=i;j<=maxp;j+=i)
                        prim[j]=0;
                    div[++k]=i;
                }
        }
}
void backt (int s,int nr)
{

}
void solve(int a,int b)
{
    int i=1;
    s=0,p=1;
    fprim[0]=0;
    while (b>1)
    {
        for (int i=1;i<=k;++i)
            {
                if (b==1)
                    break;
                if (b%div[i]==0)
                {
                    fprim[++fprim[0]]=div[i];
                    p*=div[i];
                    while (b%div[i]==0)
                        b/=div[i];
                }
            }
    }
    int total =a;
    for (int i=1; i < (1 << fprim[0])-1 ; ++i)
    {
        int t=1;
        int nr=0;
        for (int j=1;j < fprim[0]; ++j)
            if (i & (1<<j))
                {
                    ++nr;
                    t*=fprim[j+1];
                }
        if (nr%2==1)
            total+=a/t;
        else
            total-=a/t;
    }
    printf("%d\n",total);
}

int main()
{
    freopen("pinex.in","r",stdin);
    //freopen("pinex.out","w",stdout);
    scanf("%d",&m);
    generare();
    for (int i=1;i<=m;++i)
    {
        scanf("%d%d",&a,&b);
        solve(a,b);
    }
    return 0;
}