inspectorat

#include <iostream>
using namespace std;

int phi(int n) /// Functia Totient (indicatorul lui Euler)
{ /// Intoarce numarul de numere naturale mai mici decat n si prime cu n
    float rezultat=n;   /// Initializa rezultat cu n
    for(int p=2;p*p<=n;++p) /// Consideram toti factorii primi ai n si pentru fiecare factor prim p, multiplicam rezultatul cu (1-1/p)
    {
        if(n%p==0) /// Verificam daca p este factor prim
        {
            while (n%p==0) /// Daca da, actualizam n si rezultatul
                n/=p;
            rezultat*=(1.0-(1.0/(float) p));
        }
    }
    if (n>1) /// Daca n are un factor mai mare decat sqrt(n) (poate exista cel mult un astfel de factor prim)
        rezultat*=(1.0-(1.0/(float) n));
    return (int)rezultat;
}

int cmmdc(int a,int b)
{
    int r=a%b;
    while(r!=0)
        a=b,b=r,r=a%b;
    return b;
}

int main()
{
    int n,x,y,d;
    cin>>n;
    while(n)
    {
        cin>>x>>y;
        if(x>y)
            swap(x,y);
        d=cmmdc(x,y);
        cout<<1ULL*phi(x)*phi(y)*d/phi(d)<<'\n';
        --n;
    }
    return 0;
}