#include <fstream>
#include <bitset>
#define LL long long
using namespace std;
ifstream in ("pinex.in"); ofstream out ("pinex.out");
int m,nr,n,k;
LL a,b,s;
bitset<1000010> w;
int x[50];
LL p[100001];
LL d[50];
void ciur()
{
    for(int i = 2; i <= 1000000; i++)
    {
        if(!w[i])
        {
            p[++nr]=i;
            for(int j = i+i; j <=1000000; j+=i )
            {
                w[j]=1;
            }
        }
    }
}
inline void desc()
{
    int i = 1;
    n=0;
    while(p[i]*p[i]<=b)
    {
        if(!(b%p[i]))
        {
            d[++n]=p[i];
            while(!(b%p[i]))b/=p[i];
        }
        i++;
    }
    if(b>1) d[++n]=b;
}
inline void prelSol()
{
    int n1 = 0;
    LL prod = 1;
    for(int i = 1; i <=n ;i++)
    {
        n1+=x[i];
        if(x[i])prod*=d[i];
    }
    if(n1)
    {
        if(n1%2) s = s - a/prod;
        else s = s+a/prod;
    }
}
void back()
{
    k=1;
    x[k]=-1;
    do
    {
        while(x[k]<1)
        {
            x[k]++;
            if(k==n) prelSol();
            else x[++k]=-1;
        }
        k--;
    }while(k);
}
int main()
{
    in >> m;
    ciur();
    while(m--)
    {
        in >> a >> b;
        desc();
        s=a;
        back();
        out << s << '\n';
    }
}