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

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

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

void ciur()
{
    for(int i=2;i<=1000000;i++)
        if(p[i]==0)
        {

            p[++k]=i;
            for(int j=2;j<=1000000/i;j++)
                p[i*j]=1;
        }
}

int factprimi(int b)
{
    int x=0;
    int i=1;
    while(b!=1)
    {
        if(b%p[i]==0)
        {
            fp[++x]=p[i];
            while(b%p[i]==0)
                b/=p[i];
        }
        i++;
        if(i>k or p[i]*p[i]>b)
        {
            fp[++x]=b;
            break;
        }
    }
    return x;
}

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;
    ciur();
    while(q--)
    {
        fin>>a>>b;
        k=factprimi(b);
        fout<<pinex()<<endl;
    }
    return 0;
}