#include <iostream>
#include <fstream>
#include <vector>
#define  N 1000005
#define pb push_back
using namespace std;
ifstream in("pinex.in");
ofstream out("pinex.out");
typedef long long ll;
int m,prim[100005],ind,sz,semn;
bool mark[N];
ll a,b,ad;
vector <int> bdiv;
void ciur()
{
    prim[++ind]=2;
    for(int i=3;i<N;i+=2)
    {
        if(!mark[i])
        {
            prim[++ind]=i;
            for(int j=i+i;j<N;j+=i)
            {
                mark[j]=1;
            }
        }
    }
}
ll pin(ll x,ll y)
{
    bdiv.clear();
    ll sol=x;
    for(int i=1;i<=ind;i++)
    {
        if(y%prim[i]==0)
        {
            bdiv.pb(prim[i]);
            while(y%prim[i]==0)
            {
                y/=prim[i];
            }
        }
    }
    if(y>1)bdiv.pb(y);
    sz=bdiv.size();
    for(int i=1;i<(1<<sz);i++)
    {
        semn=1;
        ad=1;
        for(int j=0;j<sz;j++)
        {
            if(i&(1<<j))
            {
                ad*=bdiv[j];
                semn=semn*(-1);
            }
        }
        sol=sol+semn*(x/ad);
    }
    return sol;
}
int main()
{
    in>>m;
    ciur();
    for(int i=1;i<=m;i++)
    {
        in>>a>>b;
        out<<pin(a,b)<<'\n';
    }
    return 0;
}