#include<cstdio>
#include<cstring>

using namespace std;

long long a,sol;
int b,nr,num[30],pr[100002],i,i1;
bool prim[1000002];

void solve()
{
    int i,j,nr1;
    long long prod;
    sol=0LL;
    for(i=1;i<(1<<nr);i++)
    {
        nr1=0;
        prod=1;
        for(j=0;j<nr;j++)
        {
            if((1<<j)&i)
            {
                nr1++;
                prod*=1LL*num[j+1];
            }
        }
        if(nr1%2==0)
        {
            sol-=a/prod;
        }
        else
        {
            sol+=a/prod;
        }
    }
    printf("%lld\n",a-sol);
    return ;
}

void ciur()
{
    int i,j;
    pr[0]=1;
    pr[1]=2;
    for(i=2;i<=1000000;i+=2)
    {
        prim[i]=true;
    }
    for(i=3;i<=1000000;i+=2)
    {
        if(!prim[i])
        {
            pr[++pr[0]]=i;
            for(j=i;j<=1000000;j+=i)
            {
                prim[j]=true;
            }
        }
    }
}

int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    int m;
    scanf("%d",&m);
    ciur();
    for(i=1;i<=m;i++)
    {
        scanf("%lld%d",&a,&b);
        i1=1;
        nr=0;
        memset(num,0,sizeof(num));
        while(b>1)
        {
            if(b%pr[i1]==0)
            {
                nr++;
                num[nr]=pr[i1];
                while(b%pr[i1]==0)
                {
                    b/=pr[i1];
                }
            }
            i1++;
        }
        solve();
    }
    return 0;
}