你有一个环，环上有 n 个正整数。你能将环切成 k 段，每段包含一个或者多个数字。

对于一个切分方案，优美程度为每段数字和的最大公约数，你想使切分方案的优美程度最大，对于 k=1,2, …,n 输出答案。

第一行一个整数 n ，表示环上的数字个数。

接下来一行包含 n 个正整数，第 i 个数 a[i] 表示环上第 i 个数。

输出 n 行，第 i 行表示切成 i 段时的最大优美程度。

7
2 3 3 3 3 3 3

20
5
2
2
1
1
1

数据规模
共 10 个测试点。
测试点 1,2 满足 n≤20 。
测试点 3,4,5 满足 a[i]≤5 。
对于所有数据，满足 1≤n≤2000, 1≤a[i]≤5×10^7 。