Description

托伦自中世纪以来就以传统姜饼闻名。年轻的尼古拉斯想在他最喜欢的商店购买一套装有姜饼饼干的 $n$ 个盒子。不过这家店有非常严格的规定：尼古拉斯最初会得到 $n$ 个已经装有饼干的盒子，其中第 $i$ 个盒子初始装有 $a_{i}$ 块饼干。然后，尼古拉斯可以订购一些额外的饼干。他需要向某些盒子中添加额外的饼干，使得所有盒子中饼干数量的最大公约数$\text{*}$等于 1。可以证明这总是可行的。

请帮助尼古拉斯计算出，为了使所有饼干数量的最大公约数等于 1，需要添加的最少饼干数量。

$\text{*}$ 多个数的最大公约数（GCD）是指能整除所有这些数的最大正整数。

Input Format

第一行包含一个整数 $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 Format

输出一行，包含一个整数，表示尼古拉斯需要添加的最少饼干数量。如果不需要添加任何饼干就能使所有饼干数量的最大公约数等于 1，则输出 0。

3
90 84 140

2

Hint

样例解释：初始时 90、84 和 140 的最大公约数是 2，因此必须添加饼干。如果只添加 1 块饼干，可能得到 91、84、140（GCD 为 7），或 90、85、140（GCD 为 5），或 90、84、141（GCD 为 3），这些都不满足要求。添加 2 块饼干（分别加到第一个和第二个盒子）后，得到 91、85、140，其 GCD 为 1，因此答案是 2。注意，如果将两块饼干都加到第一个盒子，会得到 92、84、140（GCD 为 4），这仍然不符合要求。

评分

翻译由 DeepSeek V3 完成