#include <cstdio>

using namespace std;

const int LIM=1000000;
int p[LIM+5],nrd,d[100];
void ciur()
{
    int last=0;
    p[++last]=2;
    for(int i=3;i<LIM;i+=2)
        if(p[i]==0)
        {
            p[++last]=i;
            for(int j=i+i+i;j<=LIM;j=j+i+i)
                p[j]=1;
        }

}
int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    ciur();
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        nrd=0;
        int i=1;
        while(b>1)
        {
            if(b%p[i]==0)
            {
                d[++nrd]=p[i];
                while(b%p[i]==0)
                    b/=p[i];
            }
            if(p[i]*p[i]>b)
            {
                d[++nrd]=b;
                b=1;
            }
            i++;
        }
        int sol=a;
        for(i=1;i<(1<<nrd);++i)
        {
            int cop=i,nr=1,s=0,prod=1;
            while(cop)
            {
                if(cop&1)
                {
                    s++;
                    prod*=d[nr];
                }
                cop>>=1;
                nr++;
            }
            if(s%2==0)
                sol+=a/prod;
            else
                sol-=a/prod;
        }
        printf("%d\n",sol);
    }
    return 0;
}