自中世纪起，托伦便以其传统的姜饼而闻名遐迩。小尼古拉打算在他最钟爱的一家店铺购买 $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)

详细子任务附加限制及分值如下表所示。