#include <iostream>
#include <cstdio>
#include <vector>
#define N 10000005

using namespace std;

long long a, b, n, divs[N], prim[N];
bool ciur[N];
int m;

void eratosnenes()
{
    for(long long j=4;j<=N;j+=2)
        ciur[j]=1;
    prim[++prim[0]]=2;
    for(long long i=3;i<=N;i+=2)
        if(!ciur[i])
        {
            for(long long j=2*i;j<=N;j+=i)
                ciur[j]=1;
            prim[++prim[0]]=i;
        }
}

void divizori()
{
    long long nt=0, nd=1;
    while(prim[nd]*prim[nd]<=b)
    {
        if(b%prim[nd]==0)
        {
            divs[++nt]=prim[nd];
            while(b%prim[nd]==0)
                b=b/prim[nd];
        }
        nd++;
    }
    if(b>1)
        divs[++nt]=b;

    for(long long i=1;i<(1<<nt);i++)
    {
        long long nr=0, p=1;
        for(long long j=0;j<nt;j++)
            if((1<<j)&i)
                p=p*divs[j+1], nr++;
        if(nr%2==0)
            n=n-1LL*a/p;
        else
            n=n+1LL*a/p;
    }
}

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

    scanf("%d\n", &m);
    eratosnenes();
    for(int test=1;test<=m;test++)
    {
        n=0;
        scanf("%lld %lld\n", &a, &b);
        divizori();
        printf("%lld\n", a-n);
    }
    return 0;
}