#include <bits/stdc++.h>

#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

const int NMAX=1e6+5;

#define int long long
#define cin fin
#define cout fout

ifstream fin("pinex.in");
ofstream fout("pinex.out");

vector<int>divi;

void decompose(int x)
{
    int d=2;
    while(x!=1)
    {
        int p=0;
        while(x%d==0)
        {
            x/=d;
            p++;
        }
        if(p)
            divi.push_back(d);
        if(d*d>x && x!=1)
        {
            divi.push_back(x);
            x=1;
        }
        if(d==2)
            d=3;
        else
            d+=2;
    }
}

void solve()
{
    int a,b,i,j,mask,kon=0;
    cin>>a>>b;
    decompose(b);
    int n=divi.size();
    for(mask=1;mask<(1<<n);mask++)
    {
        int p=1;
        for(i=0;i<n;i++)
        {
            if(mask & (1<<i))
                p*=divi[i];
        }
        if(__builtin_popcount(mask)%2==0)
            kon-=a/p;
        else
            kon+=a/p;
    }
    cout<<a-kon<<"\n";
    divi.clear();
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}