Cerința

Lui Ionci ii place foarte mult matematica si informatica, asa ca s-a gandit sa creeze o operatie. Aceasta a numit-o "Happy", notata cu semnul ☺. Operatia se aplica doar numerelor naturale si dau ca rezultat tot un numar natural, conform exemplelor de mai jos:

• 2010 ☺ 2005 = 5
• 78 ☺ 54 = 6
• 999 ☺ 543 = 3
• 4 ☺ 9 = 1
• 5 ☺ 6 = 1
• 32 ☺ 24 = 8
• 10 ☺ 2 = 2

Profesorul de matematica, Vasy, i-a promis nota 10 pe invenție dacă pentru mai multe perechi de numere naturale veți determina cel mai mic număr rezultat cu număr par de divizori al operației Happy aplicată perechilor date și cel mai mare număr rezultat al operației Happy cu număr impar de divizori.

Date de intrare

Programul citește un număr natural N și N perechi de numere naturale a b.

Date de ieșire

Programul va afișa cel mai mic și cel mai mare rezultat obținut prin operația de mai sus, cu număr par, respectiv impar de divizori, separate printr-un spațiu. Dacă nu exista rezultate care au numărul de divizori par sau numărul de divizori impar, se va afișa mesajul NU EXISTA.

Restricții și precizări

• 1 ≤ N ≤ 20
• cele 2 * N numere citite vor fi nenule și mai mici decât 1.000.000.

Exemplu

Intrare

2
87 87
1 1

Ieșire

87 1

Explicație

• rezultatul operației aplicate numerelor 87 și 87 este 87, iar numerelor 1 și 1 este 1. Numărul 87 are 4 divizori iar numărul 1 are 1 divizor. Deci 87 este cel mai mare număr cu număr de divizori par și 1 cel mai mic număr cu numărul de divizori impar.

#include <bits/stdc++.h>
using namespace std;
int cmmdc(int a,int b)
{
    int r,d;
    while(b!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    d=a;
    return d;
}
int nrdiv(int n)
{
    int cnt=0;
    for(int i=1;i*i<=n;i++)
    {
        if(n%i==0) cnt += 2;
        if(i*i==n) cnt--;
    }
    return cnt;
}
int main()
{
   int n,a,b,minim=1000000,maxim=-1;
   cin>>n;
   for(int i=1;i<=n;++i)
   {
       cin>>a>>b;
       int d=cmmdc(a,b);
       if(nrdiv(d)%2==0)
       {
           if(d<minim) minim=d;
       }
       else
        if(nrdiv(d)%2==1)
       {
           if(d>maxim) maxim=d;
       }

   }
   if(maxim==-1 || minim==1000000) cout<<"NU EXISTA";
   else
   cout<<minim << " "<<maxim;
    return 0;
}