#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
#define NMAX 1000000000
long long t,a,b,prim[100005],v[100005];
long long nr=2;
long long i=5;
void vectorprim()
{
    prim[1]=2;
    prim[2]=3;
    while(i<=NMAX)
    {
        long long  j=1;
        while(i%prim[j]&&prim[j]*prim[j]<=i&&j<=nr)j++;
        if(prim[j]*prim[j]>i||j>nr)
        {
            prim[++nr]=i;
        }
        i+=2;
    }
}
int main()
{
    vectorprim();
    fin>>t;
    long long rez=0;
    while(t)
    {
        t--;
        fin>>a>>b;
        long long i=1;
        long long  nr=0;
        while(prim[i]*prim[i]<=b&&b>1)
        {
            if(b%prim[i]==0)
            {
                v[++nr]=prim[i];
                while(b%prim[i]==0&&b>1)
                {
                    b/=prim[i];
                }
            }
            i++;
        }
        if(b>1)v[++nr]=b;
        rez=a;
        long long lim=1LL<<nr;
        long long j;
        for(i=1; i<=nr; i++)
        {
            long long nrs=0;
            long long  p=1;
            for(j=0; j<nr; j++)
            {
                if(i&(1LL<<j))
                {
                    nrs++;
                    p*=v[j+1];
                }
            }

            if(nrs%2)
            {
                rez-=a/p;
            }
            else rez+=a/p;
        }

        fout<<rez<<'\n';

    }
    return 0;
}