题目描述

lbw 想在商店购买一套装有饼干的 $n$ 个盒子。

不过这家店有非常严格的规定：lbw 最初会得到 $n$ 个已经装有饼干的盒子，其中第 $i$ 个盒子初始装有 $a_{i}$ 块饼干。然后，lbw 可以订购一些额外的饼干。他需要向某些盒子中添加额外的饼干，使得所有盒子中饼干数量的最大公约数$\text{*}$等于 1。可以证明这总是可行的。

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

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

输入格式

第一行包含一个整数 $n$，表示盒子的数量。

第二行包含 $n$ 个整数 $a_{1}, a_{2}, \ldots, a_{n}$，其中第 $i$ 个整数 $a_{i}$ 表示第 $i$ 个盒子初始的饼干数量。

输出格式

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

输入样例

3
90 84 140

输出样例

2

说明提示

样例解释：初始时 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），这仍然不符合要求。

评分

输入样例 #2

2
2 4

输出样例 #2

1

输入样例 #3

3
7901968 6917480 5222115

输出样例 #3

0

数据范围

（$2 \leq n \leq 10^6$）

（$1 \leq a_{i} \leq 10^7$）