Jest rok 65536. Ludzie potrafią odbywać podróże międzygwiezdne. Wytyczyli nawet specjalne trasy, po których mogą poruszać się z niewyobrażalnymi prędkościami ich statki kosmiczne. Trasy te łączą różne planety, gwiazdy, a nawet galaktyki. Przy każdym takim kosmicznym szlaku są rozmieszczone w regularnych odstępach rozmaite punkty usługowe, które zapewniają podróżnym różnorodne rozrywki (sklepy, kina itd.).

W drogę między dwoma bardzo odległymi planetami wybrał się pewien jegomość. Aby urozmaicić sobie podróż, ma on zamiar korzystać z wszelkiego rodzaju atrakcji, które czekają po drodze. Niestety nie lubi on częstych przystanków i chce po drodze zatrzymać się tylko raz, odwiedzając przy okazji wszystkie ciekawe punkty. Problem w tym, że rozmaite atrakcje mogą być rozmieszczone w różnych odstępach (przykładowo kina pojawiają się co x kilometrów, restauracje co y kilometrów itd.) i wówczas bardzo rzadko znajdują się w jednym miejscu. Jeśli dany punkt usługowy jest rozmieszczony przy trasie co x kilometrów, to znaczy, że jego pierwsze wystąpienie ma miejsce po x kilometrach trasy, drugie po 2*x kilometrach itd. Napisz program, który na podstawie informacji o rozmieszczeniu atrakcji, obliczy po ilu kilometrach kosmicznej podróży nasz szanowny jegomość będzie mógł się zatrzymać i skorzystać w jednym miejscu z wszystkich rozrywek.

Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1 ≤ N ≤ 100)

zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych

W pierwszej linii zestawu danych podana jest liczba n (1 ≤ n ≤ 10) oznaczająca liczbę rozmaitych atrakcji czekających przy trasie. W kolejnym wierszu podanych jest n liczb całkowitych oddzielonych spacją i opisujących częstość występowania atrakcji: liczba di (1 ≤ di < 2⁶³) oznacza, co ile kilometrów pojawia się i-ta atrakcja.

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 ma być liczba całkowita oznaczająca odległość (w kilometrach), po której przy trasie pojawią się w jednym miejscu wszystkie atrakcje.

Wynik jest liczbą mniejszą niż 2⁶³.

Przykład
Dane wejściowe

2
2
12 16
3
40 35 25

Wynik

48
1400