Dzielniki kontratakują

To zadanie pochodzi z Kółka Informatycznego w Staszicu.

Mamy na tablicy napisane dwie liczby, A i B. Jeśli dla pewnej liczby pierwszej P, A i B są podzielne przez P, to możemy zmazać A i B i napisać zamiast nich A/P i B/P. Ponadto, jeśli A jest podzielne przez P, a B jest podzielne przez P² to możemy liczby A i B zastąpić przez A/P i B/(P²). Jakie dwie liczby o najmniejszej sumie możemy otrzymać na tablicy?

Wejście

W pierwszej linii N < 10000 - liczba zestawów danych. W każdej z kolejnych linii dwie dodatnie liczby całkowite, A i B, mniejsze niż 10¹⁸.

Wyjście

N linii, w każdej z nich dwie liczby, odpowiedź na pytanie postawione w zadaniu.

Przykładowe wejście

5
3 6
17 8
2 4
4 2
70 84

Przykładowe wyjście

1 2
17 8
1 1
2 1
5 3