自中世纪起，托伦便以其传统的姜饼而闻名遐迩。小尼古拉打算在他最钟爱的一家店铺购买 $n$ 盒姜饼。您需要协助他完成这次购买，但这家店铺的规定颇为严格：初始时，尼古拉会获得 $n$ 个已装有姜饼的盒子，其中第 $i$ 个盒子最初装有 $a_i$ 块姜饼。之后，他可以额外订购若干姜饼，并将这些姜饼添加至某些盒子中，目标是使所有盒子内姜饼数量的最大公约数变为 $1$。可以证明，这一目标总是能够实现的。
您的任务是帮助尼古拉计算，为达成上述目标（即所有盒子中姜饼数量的最大公约数为 $1$），所需添加的最少姜饼总数。
输入格式 (Input)
第一行包含一个整数 $n$ $(2 \leq n \leq 10^6)$，表示姜饼盒子的数量。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq 10^7)$，其中第 $i$ 个整数 $a_i$ 表示第 $i$ 个盒子中最初的姜饼数量。
输出格式 (Output)
输出一行，包含一个整数，即尼古拉为了使所有盒子中姜饼数量的最大公约数变为 $1$ 而需要添加的最少姜饼总数。如果初始状态下各盒姜饼数量的最大公约数已为 $1$，则输出 $0$。
样例 (Example)
输入：
3 90 84 140
输出：
2
说明：
初始时，盒子中的姜饼数量为 $90, 84, 140$，其最大公约数（GCD）为 $2$，因此需要添加姜饼。 若只添加一块姜饼，可能的情况有：
- $91, 84, 140$（GCD 为 $7$）
- $90, 85, 140$（GCD 为 $5$）
- $90, 84, 141$（GCD 为 $3$）
这些情况均未能使 GCD 变为 $1$。
若添加两块姜饼，例如，向第一个盒子添加一块，向第二个盒子添加一块，使得数量变为 $91, 85, 140$，此时 GCD 为 $1$。因此，最少需要添加 $2$ 块姜饼。
值得注意的是，若将两块姜饼都添加到第一个盒子，得到 $92, 84, 140$，其 GCD 为 $4$，这并不能达成目标。
子任务与评分 (Scoring)
详细子任务附加限制及分值如下表所示。
| 子任务编号 | 附加限制 | 分值 |
|---|---|---|
| $1$ | $n = 2$ | $17$ |
| $2$ | $n \leq 10$ | $34$ |
| $3$ | $n \leq 1000$ | $11$ |
| $4$ | 无附加限制 | $38$ |