小 Daniel 有一袋糖果和 $N$ 张卡片。

每张卡片上都写有一个正整数 $P_i$。当 Daniel 正在吃糖果时，他想到了一个有趣的游戏。他可以用绳子把两张编号为 $a$ 和 $b$ 的卡片系在一起，然后他必须吃掉 $\min(P_a \bmod P_b, P_b \bmod P_a)$ 颗糖果，其中运算符 $x \bmod y$ 表示 $x$ 除以 $y$ 的余数。

他希望将若干对卡片系在一起，使得当他提起其中任意一张卡片时，其余所有卡片也都会被一起提起。每张卡片都可以直接用绳子与任意数量的其他卡片相连。由于 Daniel 正在注意自己的身材，他不想吃太多糖果，因此他请求你计算出使所有卡片都连通所需吃掉的糖果的最小数量。

输入格式

输入第一行包含一个正整数 $N$（$1 \le N \le 10^5$）。

接下来 $N$ 行，每行包含一个正整数 $P_i$（$1 \le P_i \le 10^7$）。

输出格式

输出第一行也是唯一的一行，包含任务所要求的最小值。

子任务

• 在占总分 $30\%$ 的测试数据中，满足 $N \le 10^3$。
• 在占总分 $40\%$ 的测试数据中，满足 $P_i \le 10^6$。
• 在占总分 $70\%$ 的测试数据中，上述两个条件中至少有一个满足。

样例

输入样例 1

4
2
6
3
11

输出样例 1

1

输入样例 2

4
1
2
3
4

输出样例 2

0

输入样例 3

3
4
9
15

输出样例 3

4

说明

样例 1 说明：

Daniel 可以连接第一张和第二张卡片并吃掉 $0$ 颗糖果，连接第二张和第三张卡片并吃掉 $0$ 颗糖果，连接第一张和第四张卡片并吃掉 $1$ 颗糖果。