Description

大家的袜子谁的颜色最多都已经知道了，现在老师又想让大家拥有相同数量的袜子。于是老师让所有人依次按顺时针围成一圈，当老师说开始的时候，每个人都同时把自己袜子的一半给右边的人，如果哪一个人手中袜子的数量为奇数个就先从老师那里拿一只袜子再分一半给右边的人，直到所有人手中的袜子数相同才结束。问最后每个人手中有多少只袜子。

Input

有多组数据输入，第一行输入n(n<=100)，表示有n个人，接下来n行，第i行一个整数a[i]表示初始时第i个人手中的袜子数(a[i]≤1000)。当n为0时结束输入，结果不用输出。

Output

对于每组数据，输出最后每个人手中的袜子数相同时候的袜子。

Sample Input

6
36
2
2
2
2
2
11
22
20
18
16
14
12
10
8
6
4
2
2
2
0
0

Sample Output

14
22
1

HINT

Source

NBU OJ