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

using namespace std;

int n;
long long a, b;
bitset <1000010> ciur;
long long d[1000010];
int k;

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

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

}

long long secv()
{

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

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

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

    return 0;
}