#include <cstdio>

using namespace std;

bool ciur[1000005];

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

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

void diviz(int 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;
}

int generare()
{
    int nr=(1<<(k+1));
    int s=0;
    for(int i=1; i<=nr-1; i++)
    {
        int prod=1;
        int nre=0;
        for(int j=0; j<(k+1); j++)
        {
            if((i & (1<<j)) != 0)
            {
                prod*=div[j];
                nre++;
            }
        }
        if(nre%2 == 0)
            s-=(a/prod);
        else
            s+=(a/prod);
    }
    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("%d %d", &a, &b);
        diviz(b);
        printf("%d\n", a-generare());
        zero();
    }

    return 0;
}