Przekładnie

Treść

Podlaska Agencja Kosmiczna, pomimo braku medialnego nagłośnienia, jest przez fachowców typowana na przyszłego globalnego lidera podboju kosmosu. Dzieje się tak ze względu na ogromną ilość przełomowych rozwiązań stosowanych w projektach Agencji. Inżynierowie skupiają się tu przede wszystkim na ekonomii wytwarzanych podzespołów tak, by koszty przedsięwzięć kosmicznych nie były barierą w przeprowadzaniu ich na szeroką skalę.

Jednym z takich rozwiązań jest układ napędowy statku kosmicznego. Składa się on z jednego prostego silnika oraz wielu przekładni przekazujących jego moc do wszystkich odbiorników. Każda z przekładni działa w układzie 1:a (zwiększenie prędkości obrotowej a razy) lub a:1 (zmniejszenie prędkości obrotowej a razy). Przy połączeniu przekładni w łańcuch można uzyskać prawie dowolne przełożenie całkowite takiego układu.

Właśnie dowiedziałeś się, że Twoje podanie o przyjęcie na staż do PAK zostało zaakceptowane. Niestety nie od razu będziesz mógł zająć się badaniem prędkości nadświetlnych i innymi interesującymi zagadnieniami. Na początek postawiono przed Tobą zadanie zrobienia porządków po poprzedniku. Poprzednik ów zajmował się łączeniem przekładni w łańcuchy. Niestety nie pozostawił po sobie żadnej dokumentacji i nie wiadomo teraz jakie jest całkowite przełożenie łańcucha. Na szczęście zachowały się parametry i kolejność ułożenia pojedynczych przekładni. Napisz program, który na podstawie tych danych obliczy przełożenie całego układu.

Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=20) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych

Pierwszy wiersz zestawu danych zawiera liczbę całkowitą n (1<=n<=10⁶) przekładni w łańcuchu. W kolejnych n wierszach podane są opisy poszczególnych przekładni. Pojedynczy opis składa się z dwóch liczb całkowitych a_i i b_i (1<=a_i,b_i<=10⁶) definiujących przełożenie a_i:b_i, przy czym zawsze jedna z tych liczb jest równa 1.

Wyjście

Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu jest para liczb całkowitych a i b, oddzielonych pojedynczą spacją, oznaczających przełożenie całego łańcucha przekładni. Ze względu na to, iż taka sama wartość przełożenia może być podana na wiele sposobów, np. 1:2 i 2:4, jako wynik należy wypisać tę parę, dla której wartość a jest najmniejsza z możliwych. Dane wejściowe są tak dobrane, że wartości a i b nie przekraczają 10⁹.

Przykład

dane wejściowe:
3
3
4 1
1 6
3 1
3
1 27
3 1
9 1
4
1 500000
1 300000
1000000 1
200000 1

wynik:
2 1
1 1
4 3