#include <fstream>
#include <cstdio>
#define Nmax 1000000
#define LL long long
using namespace std;

ofstream g("pinex.out");

int n,C[Nmax+1],nrp,x;
LL a,b,v[50];

void ciur()
{
    for (LL i=2;i<=Nmax;i++)
    {
        if (C[i]==0)
        {
            C[++nrp] = i;
            for (LL j=i*i;j<=Nmax;j+=i)
                C[j] = 1;
        }
    }
}


int main()
{
    freopen("pinex.in","r",stdin);

    ciur();

    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d %d",&a,&b);
        x=0;
        for (int j=1;j<=nrp;j++)
        {
            if (b%C[j]==0)
                v[++x] = C[j];
        }

        int mx = (1<<x)-1;
        LL rez = 0;
        for (int i=1;i<=mx;i++)
        {
            int sav = i,nr = 0,val = 1,poz = 1;
            while (sav!=0)
            {
                if (sav%2==1)
                {
                    nr++;
                    val*=v[poz];
                }
                poz++;
                sav/=2;
            }
            if (nr%2==1)
                rez+=a/val;
            else
                rez-=a/val;
        }

        g<<a-rez<<'\n';
    }

    return 0;
}