#include <cstdio>
#define tip long long
using namespace std;
tip A,b,a[2000],d,F[15],sol;
int m,k,i;
int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%d",&m);
    a[0]=1;
    for(;m;m--)
    {
        scanf("%lld%lld",&A,&b);
        k=0;
        if(b%2==0)
        {
            F[k++]=2;
            while(b%2==0)b/=2;
        }
        for(d=3;d*d<=b;d+=2)
            if(b%d==0)
            {
                F[k++]=d;
                while(b%d==0)b/=d;
            }
        if(b>1)
            F[k++]=b;
        for(i=0;i<k;i++)
            a[1<<i]=-F[i];
        k=(1<<k);
        for(sol=0,i=0;i<k;i++)
        {
            a[i]=a[i&(-i)]*a[i-(i&(-i))];
            sol+=A/a[i];
        }
        printf("%lld\n",sol);
    }
    return 0;
}