#include <fstream>
#define MAXD 20
#define MAX 1000005
#define ll long long
using namespace std;
ifstream fi("pinex.in");
ofstream fo("pinex.out");



ll m,a,b;
bool ciur[MAX];
int div[MAXD],k;

bool prim(ll x)
{
    for (int i=2; 1LL*i*i<=x; i++)
        if (x%i==0)
            return 0;
    return 1;
}

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

int main()
{
    eratostene();
    ciur[0]=ciur[1]=1;

    /*for (int i=2; i<=100; i++)
        if (ciur[i]==0)
            fo<<i<<" este prim\n";
        else
            fo<<i<<" nu este prim\n";*/

    fi>>m;
    while (m--)
    {
        fi>>a>>b;
        k=0;
        ll aux=b;
        for (int i=2; i*i<=b; i++)
            if (b%i==0)
            {
                if (ciur[i]==0)
                    div[++k]=i;
                while (aux%i==0)
                    aux/=i;
            }
        if (aux>1)
            div[++k]=aux;

        /*for (int i=1; i<=k; i++)
            fo<<div[i]<<" ";
        fo<<"\n";
        return 0;*/

        ll cardinal=0;

        for (int mask=1; mask<(1<<k); mask++)
        {
            ll numar=1; /// produsul nr prime din submultime
            //ll curent;
            int biti=0; /// nr de biti de 1
            for (int i=0; i<k; i++)
            {
                if ((mask>>i)&1) /// i+1 apare in submultime
                {
                    biti++;
                    numar*=div[i+1];
                }
            }
            ll ap=a/numar; /// cardinalul curent
            if (biti%2==0)
                cardinal-=ap;
            else
                cardinal+=ap;
        }
        fo<<a-cardinal<<"\n";
    }

    return 0;
}