#include <cstdio>
#include <bitset>
#include <string.h>

using namespace std;

long long int n, a, b;
bitset <1000005> ciur;
long long d[1000005];
long long o = 0;

long long prim[100001000];
long long k=1;

void ciu()
{
    for(int i=2; i<=1000005; i++)
        if(ciur[i] == 0)
        {
            prim[k++] = i;
            for(int j=i+i; j<=1000005; j+=i)
                ciur[j] = 1;
        }
}


void diviz()
{
    for(long long di=1; prim[di]*prim[di] <= b; di++)
    {
        if(b%prim[di] == 0)
        {
            while(b%prim[di] == 0)
                b/=prim[di];
            d[o++] = prim[di];
        }
    }
    if(b != 1)
        d[o++] = b;
}


long long subsir()
{
    long long nr=(1<<o);
    long long s=0;
    for(long long i=1; i<nr; i++)
    {
        long long p=1;
        long long nre=0;
        for(long long j=0; j<o; j++)
            if(i&(1<<j))
            {
                p=p*d[j];
                nre++;
            }
        if(nre%2 == 0)
            s=s-a/p;
        else s=s+a/p;
    }
    s = a-s;
    return s;
}



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


    scanf("%lld", &n);
    ciu();
    for(int i=1; i<=n; i++)
    {
        scanf("%lld %lld", &a, &b);
        diviz();
        printf("%lld\n", subsir());
        memset(d, 0, 1000005);
        o=0;
    }
    return 0;
}