#include <fstream>
using namespace std;

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

int q,b,k;
long long a, fp[55],r;

int factprimi(int b)
{
    k=0;
    int d=2;
    if(b%2==0)
    {
        fp[++k]=2;
        while(b%2==0)
            b/=2;
    }
    for(d=3;d*d<=b;d+=2)
    {
        if(b%d==0)
        {
            fp[++k]=d;
            while(b%d==0)
                b/=d;
        }
    }
    if(b!=1)
        fp[++k]=b;
    return k;
}
int pinex()
{
    int r=a;
    int lim=(1<<k)-1;
    for(int i=1;i<=lim;i++)
    {
        int p=1;
        int cnt=0;
        for(int j=0;(1<<j)<=i;j++)
            if((i&(1<<j))!=0)
            {
                cnt++;
                p=p*fp[j+1];
            }
        if(cnt%2==1)
            r=r-a/p;
        else
            r=r+a/p;
        //fout<<r<<" "<<a<<" "<<p<<endl;
    }
    return r;
}

int main()
{
    fin>>q;
    while(q--)
    {
        fin>>a>>b;
        k=factprimi(b);
        fout<<pinex()<<endl;
    }
    return 0;
}