有一叠卡片，共有 $N$ 张，编号从 $1$ 到 $N$，其中第 $i$ 张卡片上写着一个正整数 $A_i$。

你需要对这些卡片进行 $N - 1$ 次操作。在每次操作中，你可以从牌堆中任选两张卡片。设选出的两张卡片上的整数分别为 $x$ 和 $y$。移除这两张卡片，并向牌堆中加入一张写有 $2 \cdot \gcd(x, y)$ 的新卡片，其中 $\gcd(x, y)$ 表示 $x$ 和 $y$ 的最大公约数。注意，经过这一次操作，牌堆中的卡片数量会减少一张（因为移除了两张并加入了一张）。

在执行完所有 $N - 1$ 次操作后，牌堆中将只剩下一张卡片。你的目标是使最后这张卡片上的整数尽可能大；请输出这个整数。

输入格式

输入的第一行包含一个整数 $N$ ($2 \le N \le 100\,000$)，表示卡片的数量。下一行包含 $N$ 个整数 $A_i$ ($1 \le A_i \le 10^9$)，表示第 $i$ 张卡片上写的数字。

输出格式

输出一行一个整数，表示最后一张卡片上可能的最大整数。

样例

输入 1

3
2 4 6

输出 1

8

说明 1

为了使最后一张卡片上的整数最大，你需要在第一次操作中选择第 1 张和第 3 张卡片，此时 $x = 2$，$y = 6$。移除这两张卡片，并加入一张写有 $2 \cdot \gcd(2, 6) = 4$ 的新卡片。第二次操作时，牌堆中剩下两张写有 $4$ 的卡片。选择这两张卡片，此时 $x = 4$，$y = 4$。移除它们并加入一张写有 $2 \cdot \gcd(4, 4) = 8$ 的新卡片。最后一张卡片上的数字为 $8$，这是该样例中可能的最大值。

输入 2

3
3 5 7

输出 2

2

说明 2

无论你在每次操作中如何选择，答案始终为 $2$。

输入 3

4
9 9 9 9

输出 3

36

输入 4

5
10 100 1000 10000 100000

输出 4

160