#include <fstream>
#include <math.h>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int m, i, j, k, t, v[100010], n;
long long a, b, u, p, d[20], s, aux;
bool x[1000010];

void ciur(){
    for(i=2; i<1000001; i++)
        if(x[i]==0)
        {
            v[++k]=i;
            for(j=i+i; j<1000001; j+=i)
                x[j]=1;
        }
}

int main(){
    ciur();
    f>>m;
    for(i=1; i<=m; i++)
    {
        f>>a>>b;
        u=b;
        s=0;
        t=0;
        j=1;
        aux=sqrt(b*1.0);
        while(u!=1 && v[j]<=aux)
        {
            if(u%v[j]==0)
            {
                d[++t]=v[j];
                while(u%v[j]==0)
                    u=u/v[j];
            }
            j++;
        }
        if(u!=1)
            d[++t]=u;
        for(j=0; j<=t; j++)
            x[j]=0;
        while(x[0]!=1)
        {
            j=t;
            while(x[j]==1)
            {
                x[j]=0;
                j--;
            }
            x[j]=1;
            if(x[0]==1)
                break;
            p=1;
            n=0;
            for(j=1; j<=t; j++)
                if(x[j]==1)
                {
                    n++;
                    p*=d[j];
                }
            if(n%2==0)
                s-=a/p;
            else
                s+=a/p;
        }
        g<<a-s<<"\n";
    }
    return 0;
}