#include <bits/stdc++.h>
#define ULL unsigned long long

using namespace std;

ifstream in("pinex.in");
ofstream out("pinex.out");

int t;
ULL a,b;

int prim[100001],nrP;
bitset <1000001> cr;

ULL divB[21];
int nrD;

void ciur()
{
    for(int i=2;i<=1000000;i++)
        if(!cr[i])
        {
            prim[++nrP]=i;

            for(int j=i;j<=1000000/i;j++)
                cr[i*j]=1;
        }
}

int main()
{
    ciur();

    in>>t;

    while(t--)
    {
        in>>a>>b;
        nrD=0;

        for(int i=1;i<=nrP && b!=1;i++)
            if(b%prim[i]==0)
            {
                divB[++nrD]=prim[i];

                while(b%prim[i]==0)
                    b/=prim[i];
            }

        if(b>1)
            divB[++nrD]=b;

        int fin=1<<nrD;
        ULL sum=a;

        int nrI;
        ULL divr;

        for(int i=1;i<=fin-1;i++)
        {
            nrI=0;
            divr=1;

            for(int j=0;j<nrD;j++)
                if( i&(1<<j) )
                {
                    nrI++;
                    divr*=divB[j+1];
                }

            if(nrI%2)
                sum-=a/divr;
            else
                sum+=a/divr;
        }

        out<<sum<<'\n';
    }

    return 0;
}