#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long

using namespace std;
/*#define cin in
#define cout out
ifstream in ("pinex.in");
ofstream out ("pinex.out");*/

int a,b;
vector <int> divv;

int bld()
{
    int k=(1LL<<divv.size());
    int sum=0;
    for (int i=1; i<k; i++)
    {
        int cnt=0; int part=1;
        for (int pos=0; pos<divv.size(); pos++)
        {
            if (i & (1LL<<pos))
            {
                cnt++; part*=divv[pos];
            }
        }
        if (part>a) continue;
        if (cnt%2==1) sum+=a/part;
        else sum-=a/part;
    }

    return a-sum;
}

void solv()
{
    divv.clear();
    int d=2;
    while (b>1)
    {
        int cnt=0;
        while (b%d==0)
        {
            b/=d; cnt++;
        }
        if (cnt) {divv.push_back(d);}
        d++;

        if (b>1 && d*d>=b) d=b;
    }

    cout<<bld()<<"\n";
}

signed main()
{
    int t; cin>>t;
    while (t--)
    {
        cin>>a>>b;
        solv();
    }
}