#include <bits/stdc++.h>
#ifdef LOCAL
#define in cin
#define out cout
#endif
#define int int64_t
using namespace std;

#ifndef LOCAL
ifstream in("pinex.in");
ofstream out("pinex.out");
#endif

const int nmax = 1e6+5;

vector<int> primes;
bool ciur[nmax];

void doCiur()
{
    primes.push_back(2);
    for(int i=3;i<nmax;i+=2)
    {
        if(!ciur[i])
        {
            primes.push_back(i);
            for(int j=i*i;j<nmax;j+=i)
            {
                ciur[j]=1;
            }
        }
    }
}

vector<int> getDivs(int nr)
{
    vector<int> res;
    for(auto i:primes)
    {
        if(nr%i==0)res.push_back(i);
    }
    for(auto i:primes)
    {
        while(nr%i==0)
        {
            nr/=i;
        }
    }
    if(nr!=1)res.push_back(nr);
    //for(auto i:res)cerr<<i<<' ';
    //cerr<<'\n';
    return res;
}

int a,b;

void bkt(vector<int> &divs, int &res, int ind=0,int prod=1,int cnt=0)
{
    if(ind==divs.size())
    {
        if(cnt==0)return;
        //cerr<<prod<<'\n';
        if(cnt%2==1)
        {
            res+=a/prod;
        }
        else
        {
            res-=a/prod;
        }
    }
    else
    {
        bkt(divs,res,ind+1,prod*divs[ind],cnt+1);
        bkt(divs,res,ind+1,prod,cnt);
    }
}

void solve()
{
    in>>a>>b;
    auto v = getDivs(b);
    int res=0;
    bkt(v,res);
    cout<<a-res<<'\n';
}

signed main()
{
    doCiur();
    int t;in>>t;
    while(t-->0)
    {
        solve();
    }
}