Asad is a student of class 6. He loves to learn new logic from Number Theory. He receives a gift from his Mom named “LCM game”. In the game, He is given some integer and he need to find the LCM of the given integers. But he is facing some problem to find the LCM of more than two integers.

In this case, He ask for your help to find the LCM of given N integers. As you are a great programmer in our country.

Input

Every line of input contains a single integer N denoting the number of integers (until EOF) that is given to him.

Next line contain N spaces separated integer x₁,x₂,x₃,………,x_n.

Constraints:

1<=N<= 10⁵

1<=x_i<=10⁹

Output

For each input, print a single line and the value of the LCM of N integers.

Example

Input:
2
1 2
3
2 3 4

Output:
2
12

2
1 2
3
2 3 4

Note: In second test case, LCM(2,3) = 6 and LCM(6,4) = 12