#include <fstream>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
bool ciur[1000001];
ll k,fct[500001],fact[100001],a,b,i,j,test,ii;
int main()
{
    fill(ciur+2,ciur+1000000,1);
    k=0;
    for(i=2;i<=1000000;i++)
    {
        if(ciur[i]==0) continue;
        for(j=i*i;j<=1000000;j=j+i) ciur[j]=0;
        fct[++k]=i;
    }
    f>>test;
    for(ii=1;ii<=test;ii++)
    {
        f>>a>>b;
        ll t=0,d=1;
        while(b>1)
        {
            d++;
            if(b%fct[d]==0)
            {
                fact[++t]=fct[d];
                while(b%fct[d]==0) b/=fct[d];
            }
            if(1ll*fct[d]*fct[d]>b&&b>1)
            {
                fact[++t]=b;
                b=1;
            }
        }
        ll sol=a;
        for(i=1;i<(1<<t);i++)
        {
            ll nr = 0, prod = 1;
                for (int j = 0; j < t; j++)
                    if ((1 << j) & i) {
                        prod = 1LL * prod * fact[j + 1];
                        nr++;
                    }
            if (nr % 2) nr = -1;
            else nr = 1;
            sol = sol + 1LL * nr * a / prod;
        }
        g<<sol<<'\n';
    }
    return 0;
}