#include <iostream>
#include <fstream>
#include <vector>
#define int long long
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
vector <int> v,prim;
bool ciur[100005];
int n,a,b;
void precalc()
{
    ciur[1]=1;
    ciur[0]=1;
    for (int i=2; i*i<=100000; i++)
        if (!ciur[i]) for (int j=i*i; j<=100000; j+=i)
                ciur[j]=1;
    for (int i=2;i<=100000;i++)
        if (!ciur[i]) prim.push_back(i);
}
int sub(int n)
{
    int l=1<<n,s=0;
    for (int i=1; i<=l; i++)
    {
        int p=1,nr=0;
        for (int j=0; j<n; j++)
        {
            if (i & (1<<j)) p=p*v[j],nr++;
        }
        //cout<<p<<' ';
        if (nr%2==0) s+=a/p;
        else s-=a/p;
    }
    //cout<<'\n';
    return s;
}
int32_t main()
{
    int m;
    fin>>m;
    precalc();
    for (; m; m--)
    {
        fin>>a>>b;
        int c=b,k=0,d=prim[k];
        while (d*d<=c)
        {
            int e=0;
            while (c%d==0)
            {
                c/=d;
                e++;
            }
            if (e) v.push_back(d);
            k++;
            d=prim[k];
        }
        if (c!=1) v.push_back(c);
        //cout<<v.size()<<' ';
        fout<<sub(v.size())<<'\n';
        v.clear();
    }

    return 0;
}