Description

有一天，小明在上课，老师现在有一个问题，有n个数，任意取一个数x，这个x可以变成任意的数（1<=x<=10^9),现在需要求出这n个数最大的GCD（最大公约数），老师提问到小明了，小明不会这个，现在小明需要你的帮助，你能帮助小明吗？

Format

Input

第一行输入一个数n（2<=n<=10^5)

第二行输入n个数a（1<=a<=10^9)

Output

输出n个数最大的GCD

Samples

3
7 6 8

2

3
12 15 18

6

Hint