#include <fstream>


using namespace std;

bool  v[1000001];
int p[80000];

void ciur(int n)
{
    v[0]=v[1]=1;

    for(int i=4; i<=n; i+=2)
        v[i]=1;

    for(int i=3; i*i<=n; i+=2)
        if(v[i]==0)
            for(int j=i*i; j<=n; j+=2*i  )
                v[j]=1;
}

long long d[15];

int main()

{
  ifstream cin("pinex.in");
  ofstream cout("pinex.out");
    ciur(1000000);
    int cnt=0;
    for(int i=2; i<=1000000; i++)
        if(v[i]==0)
        {
            cnt++;
            p[cnt]=i;
        }
    //  p[1].......p[cnt]   cnt=78498
    int m;
    cin>>m;
    while(m)
    {
        long long a, b;
        cin>>a>>b;
        // d[0].....d[k-1] k=nr de divizori primi
        int ind = 1;
        int k=0;
        while(p[ind]*p[ind]<=b && b>1 )
        {
            if(  b%p[ind]==0 )
            {
                while( b%p[ind]==0 )  b/=p[ind];
                d[k]=p[ind];
                k++;

            }
            ind++;
        }
        if(b>1)
        {
            d[k]=b;
            k++;
        }
        // d[0].....d[k-1] k=nr de divizori primi
        int x,j,s;
        long long contor,suma=0;
        for(x=1; x<(1<<k); x++)
        {
            contor=0;
            long long div=1;
            for(j=0; j<k; j++)
                if(x&(1<<j))
                {
                    contor++;
                    div*=d[k-j-1];
                }
            if(contor%2==0)
                suma-=(a/div);
            else
                suma+=(a/div);
        }
        cout<<a-suma<<'\n';
        m--;
    }


    return 0;
}