Inspectoratul școlar județean organizează un concurs pentru ocuparea strategicului post de fochist. La proba de informatică, cea mai importantă a concursului, candidații au de rezolvat următoarea problemă.

Cerința

Se dau n perechi de numere naturale și pentru fiecare pereche (x,y) trebuie să se afle câte numere naturale nenule strict mai mici decât produsul x * y sunt prime cu x * y.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n perechi de numere naturale x și y.

Date de ieșire

Programul va afișa pe ecran, pentru fiecare pereche (x, y) valoarea cerută, urmată de enter.

Restricții și precizări

• 1 ≤ n ≤ 10 000
• Pentru fiecare pereche (x, y), 2 ≤ x, y ≤ 200 000
• Două numere sunt prime între ele dacă cel mai mare divizor al lor este 1.
• Atenție, produsul a două numere poate depăși valoarea maximă admisă de tipul int.
• Această ultimă precizare este disponibilă numai inspectorilor.

Exemplu

Intrare

3
3 4
3 3
97 33

Ieșire

4
6
1920

Explicație

Pentru prima pereche: 3 * 4 = 12, iar 12 este prim cu patru numere: 1, 5, 7, 11. Pentru a doua pereche: 3 * 3 = 9, iar 9 este prim cu șase numere: 1, 2, 4, 5, 7, 8. Pentru a treia pereche: puteți verifica și singuri că așa este. Oricum, inspectorii nu greșesc niciodată.

#include <bits/stdc++.h>
using namespace std;

long long n , x , y;

long long Phi(long long n)
{
    long long r = n , d = 2;
    while(n > 1)
    {
        if(n % d == 0)
        {
            r = r / d * (d - 1);
            while(n % d == 0)n /= d;
        }
        d++;
        if(d * d > n)d = n;
    }
    return r;
}

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

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> x >> y;
        int d = cmmdc(x , y);
        cout << Phi(x) * Phi(y) * d / Phi(d) << '\n';
    }
}