#include <bits/stdc++.h>
#define nmax 1000005
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int n,prime[nmax/10],k,exponenti[20],lg,biti[20];
bitset<nmax>ciur;
inline void Ciur()
{
    int i,j;
    ciur[1]=1;
    for(i=4;i<=nmax;i+=2)
        ciur[i]=1;
    for(i=3;i*i<=nmax;i+=2)
        if(!ciur[i])
            for(j=i*i;j<=nmax;j+=2*i)
                ciur[j]=1;
    k=1;
    prime[k]=2;
    for(i=3;i<=nmax;i+=2)
        if(!ciur[i])
          prime[++k]=i;
}
inline void Descompunere(long long x)
{
    int d,i;
    i=1;
    d=prime[i];
    lg=0;
    while(1LL*d*d<=x && x>1 && i<=k)
    {
        if(x%d==0)
        {
            exponenti[++lg]=d;
            while(x%d==0)
                x/=d;
        }
        i++;
        d=prime[i];
    }
    if(x>1)
        exponenti[++lg]=x;
}
inline long long  Up(long long x)
{
    int p,nr,i;
    long long sol=0,s;
     for(i=1;i<=20;i++)
        biti[i]=0;
    biti[1]=1;
    p=lg+1;
    while(!biti[p])
    {
        s=1;
        nr=0;
        for(i=1;i<=lg;i++)
            if(biti[i])
        {
            nr++;
            s=1LL*s*exponenti[i];
        }
        if(nr%2)
            sol+=x/s;
        else sol-=x/s;
        for(i=1;biti[i] && i<=lg;i++)
            biti[i]=0;
        biti[i]=1;
    }
    return sol;
}
void Rezolvare()
{
    long long x,y,val;
    int i,j;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>x>>y;
        Descompunere(y);
        val=Up(x);
        cout<<val<<" ";
        fout<<x-val<<"\n";
    }
}
int main()
{
    Ciur();
    Rezolvare();
    fin.close();
    fout.close();
    return 0;
}