#include <bits/stdc++.h>
/// Template Dutzu
#define fast ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");
int d[501];
bool f[501];
long long rez;
void desc(long long x)
{
    int k=2;
    d[0]=0;
    while (k*k<=x)
    {
        if (x%k==0)
        {
            d[++d[0]]=k;
            while (x%k==0)
                x/=k;
        }
        k++;
    }
    if (x!=1)
        d[++d[0]]=x;
}
long long a,b;
void bkt(int vf, int lg)
{
    if (vf>lg)
    {
        long long aux=1;
        int cnt=0;
        for (int i=1;i<=lg;i++)
        {
            if (f[i])
            {
                aux*=d[i];
                cnt++;
            }
        }
        if (cnt%2)
            rez+=a-a/aux;
        else
            rez-=a-a/aux;
        return;
    }
    bkt(vf+1,lg);
        f[vf]=1;
    bkt(vf+1,lg);
        f[vf]=0;
}
int main()
{
    fast
    int m;
    fin>>m;
    for (int l=1;l<=m;l++)
    {
        fin>>a>>b;
        if (b==1)
        {fout<<a<<'\n';continue;}
        desc(b);
        rez=0;
        bkt(1,d[0]);
        fout<<rez<<'\n';
    }
    return 0;
}