#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
ifstream in("pinex.in");
ofstream out("pinex.out");
#define cin in
#define cout out
#endif // LOCAL

#define int long long

vector<int> prims;

const int MN = 1e6+6;

bool c[MN];
void ciur()
{
    prims.push_back(2);
    for(int i=3;i<MN;i+=2)
    {
        if(c[i]==0)
        {
            prims.push_back(i);
            for(int j=i*2;j<MN;j+=i)
            {
                c[j]=1;
            }
        }
    }
}

int n,a,b;

void solve()
{
    cin>>a>>b;
    vector<int> divs;
    for(auto e:prims)
    {
        bool ok=0;
        while(b%e==0)
        {
            b/=e;
            ok=1;
        }
        if(ok) divs.push_back(e);
    }

    if(b!=1) divs.push_back(b);


    int siz=divs.size();
    int m=(1<<siz);

    int ans=0;
    for(int i=1;i<m;i++)
    {
        int mod=-1, mult=1;
        for(int j=0;(1<<j)<=i;j++)
        {
            if((i>>j)&1) mod=-mod, mult*=divs[j];
        }
        ans+=(a/mult)*mod;
    }

    cout<<a-ans<<'\n';
}

int32_t main()
{
    cin>>n;
    ciur();
    while(n--)
    {
        solve();
    }
    return 0;
}