#include<bits/stdc++.h>
#define MOD 1000000
#define int long long
using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

int ciur[MOD+101],k=0,d[101],ans,a,b,divv[18];
int nou[1000005];

void eratosthenes()
{
    int i,j;
    for(i=2; i*i<=MOD; i++)
    {
        if(ciur[i]==0)
        {
            for(j=i*i; j<=MOD; j+=i)
                ciur[j]=1;
        }
    }
    for(i=2; i<=MOD; i++)
    {
        if(ciur[i]==0)
        {
            k++;
            nou[k]=i;
        }
    }
}

int divizori(int x)
{
    int i=1,nrdiv=0;
    for(i=1; nou[i]*nou[i]<=x && i<=k; i++)
    {
        if(x%nou[i]==0)
        {
            nrdiv++;
            divv[nrdiv]=nou[i];
            while(x%nou[i]==0)
                x/=nou[i];
        }
    }
    if(x>1)
    {
        nrdiv++;
        divv[nrdiv]=x;
    }
    return nrdiv;
}

int submultimi(int nr, int x)
{
    int val=(1<<nr)-1,i,ok,prod,card,j,ans=x;
    for(i=1;i<=val;i++)
    {
        prod=1;
        card=0;
        for(j=0;j<nr;j++)
        {
            if(i & (1<<j))
            {
                prod=1LL*prod*divv[j+1];
                card++;
            }
        }
        if(card%2==1)
            ok=-1;
        else
            ok=1;
        ans=ans+1LL*ok*x/prod;
    }
    return ans;
}

signed main()
{
    int t,l,rez;
    eratosthenes();
    f>>t;
    for(l=1;l<=t;l++)
    {
        f>>a>>b;
        rez=divizori(b);
        g<<submultimi(rez,a)<<'\n';
    }
    return 0;
}