POLSKI SPOJ

Dwie liczby a i b są ze sobą spokrewnione, jeśli istnieje taka całkowita liczba r, z przedziału [0, 4], że liczbę a otrzymujemy poprzez zmniejszenie sumy dzielników właściwych liczby b o r oraz liczbę b otrzymujemy poprzez zmniejszenie sumy dzielników właściwych liczby a o r. Liczbę r nazywamy stopniem pokrewieństwa.

Dla przykładu liczba 102 jest spokrewniona z liczbą 110, a stopień pokrewieństwa wynosi 4, liczba 496 jest spokrewniona ze sobą, a stopień pokrewieństwa wynosi 0.

Wejście

W pierwszym wierszu jedna liczba n ∈ [1, 10⁴] określająca liczbę zestawów danych. W kolejnych n wierszach znajdują się zestawy danych.

Każdy zestaw danych składa się z jednej liczby całkowitej x ∈ [2, 10⁹], dla której szukamy liczby spokrewnionej.

Wyjście

Dla każdej wczytanej liczby x należy wypisać liczbę z nią spokrewnioną oraz stopień pokrewieństwa. Jeżeli liczba jest spokrewniona z więcej niż jedną liczbą wybieramy tą o najmniejszym stopniu pokrewieństwa.

Gdy liczba x nie posiada liczby spokrewnionej należy wypisać -1.

Przykład

Wejście:

4
21
11
102
496

Wyjście:

-1
-1
110 4
496 0