#include <cstdio>

using namespace std;

bool ciur[1000010];

long long div[1000004];
int k=-1;
long long  a, b;
int m;

void ciurul()
{
    for(int i=2; i<=100005; i++)
    {
        if(ciur[i] == 0)
        {
            for(int j=i+i; j<=100005; j+=i)
                ciur[j]=1;
        }
    }
}

void diviz(long long b)
{
    if(b%2 == 0)
    {
        div[++k]=2;
        while(b%2 == 0)
            b/=2;
    }

    for(int i=3; i*i<b; i+=2)
    {
        if(ciur[i] == 0 && b%i == 0)
        {
            div[++k]=i;
            while(b%i == 0)
                b/=i;
        }
    }
    if(b != 1)
        div[++k]=b;
}

void zero()
{
    for(int i=1; i<=k; i++)
    {
        div[i]=0;
    }
    k=-1;
}

long long generare()
{
    long long nr=(1<<(k+1));
    long long s=0;
    for(int i=1; i<=nr-1; i++)
    {
        long long prod=1;
        int nre=0;
        for(int j=0; j<(k+1); j++)
        {
            if((i & (1<<j)) != 0)
            {
                prod=prod*div[j];
                nre++;
            }
        }
        if(nre%2 == 0)
            s=(s-a/prod);
        else
            s=(s+a/prod);
    }
    s=a-s;
    return s;
}

int main()
{

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

    scanf("%d", &m);
    ciurul();
    for(int i=1; i<=m; i++)
    {
        scanf("%lld %lld", &a, &b);
        diviz(b);
        printf("%lld\n", generare());
        zero();
    }

    return 0;
}