#include <fstream>
#include <vector>
#define int long long
using namespace std;
ifstream fcin("pinex.in");
ofstream fout("pinex.out");
int t,x,y;
inline int cmmmc(int a, int b)
{
    int p=a*b;
    while(b!=0)
    {
        int r=a%b;
        a=b;
        b=r;
    }
    return p/a;
}
inline void solve(int x, int y)
{
    vector <int> v;
    for(int d=2; d*d<=y; d++)
    {
        int e=0;
        while(y%d==0) e++, y=y/d;
        if(e) v.push_back(d);
    }
    if(y>1) v.push_back(y);
    int rez=0;
    for(int i=0; i<(1<<v.size()); i++)
    {
        int nr=0, m;
        for(int j=0; j<v.size(); j++)
        {
            if(((1<<j) & i) ^ 0)
            {
                if(nr==0) m=v[j];
                else m=cmmmc(m,v[j]);
                nr++;
            }
        }
        if(nr & 1) rez+=(x/m);
        else rez-=(x/m);
    }
    fout<<x-rez<<'\n';
}
signed main()
{
    fcin>>t;
    while(t--)
    {
        fcin>>x>>y;
        solve(x,y);
    }
    return 0;
}