#include <fstream>
#include <bitset>
#include <vector>
#define pb          push_back
#define all(x)      x.begin(),x.end()
using namespace std;
using i64=long long;
using u64=uint64_t;
const int mod=1e9+9;
const i64 INF=1e18;
const int inf=1e9;
const int SQRT=1e6;
vector<int>prim;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
void ciur()
{
    bitset<SQRT+1>c;
    for(int i=2;i*i<=SQRT;i++)
    {
        if(!c[i])
        {
            for(int j=i*i;j<=SQRT;j+=i)
            {
                c[j]=true;
            }
        }
    }
    for(int i=2;i<=SQRT;i++)
    {
        if(!c[i])
        {
            prim.pb(i);
        }
    }
}

vector<i64> get_factors(i64 val)
{
    vector<i64>factors;
    for(int &c:prim)
    {
        if(1LL*c*c>val)
        {
            break;
        }

        if(val%c==0)
        {
            factors.pb(c);
            while(val%c==0)
            {
                val/=c;
            }
        }
    }

    if(val!=1)
    {
        factors.pb(val);
    }

    return factors;
}


void solve()
{
    i64 a,b;
    cin>>a>>b;

    vector<i64>factors = get_factors(b);

    int n = (int)factors.size();

    i64 rez=0;
    for(int i=0;i<(1<<n);i++)
    {
        i64 val=1;
        for(int j=0;j<n;j++)
        {
            if(((i>>j)&1)>0)
            {
                val*= -factors[j];
            }
        }
        rez+=a/val;
    }
    cout<<rez<<'\n';
}
main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    ciur();
    int tt;
    cin>>tt;
    while(tt--)
    {
        solve();
    }
}