#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;

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

#define MAX 1000100

typedef long long int lli;

bool prim[MAX+10];

lli a[MAX/10],k, i, j,d[10000];

void ciur()
{
    for(i=2*2;i<=MAX;i+=2)
    {
        prim[i]=1;
    }
    for(i=3;i*i<=MAX;i+=2)
    {
        if(!prim[i])
        {
            for(j=i*i;j<=MAX;j+=i)
                prim[j]=1;
        }
    }
    for(i=2;i<=MAX;i++)
        if(!prim[i])
            a[++k]=i;
}

int main()
{
    lli t,ki,z,A,B,s,i,ci,g,l;
    ciur();
    fin>>t;
    for(ki=1;ki<=t;ki++)
    {
        s=0;
        fin>>A>>B;
        z=0;
        for(i=1;a[i]*a[i]<=B;i++)
        {
            if(B%a[i]==0)
            {
                d[++z]=a[i];
                while(B%a[i]==0)
                    B/=a[i];
            }
        }
        if(B>1)
            d[++z]=B;
        for(i=1;i<(1<<z);i++)
        {
            ci=i;
            g=1;
            k=0;
            l=0;
            while(ci)
            {
                l++;
                if(ci&1)
                {
                    k++;
                    g*=d[l];
                }
                ci>>=1;
            }
            if(k&1)
                s+=(A/g);
            else
                s-=(A/g);
        }
        fout<<A-s<<"\n";
    }
    return 0;
}