题目描述

题目译自 BalticOI 2025 Day2「Gingerbread」

托伦自中世纪以来就以其传统姜饼闻名。小尼古拉想在他最爱的店铺购买 $n$ 盒姜饼。你需要帮助他完成购买，但这家店铺的规则颇为严格：尼古拉一开始会拿到 $n$ 盒已经装好姜饼的盒子，第 $i$ 盒最初装有 $a_i$ 块姜饼。之后，他可以额外订购一些姜饼，将它们添加到某些盒子中，使所有盒子中姜饼数量的最大公约数变为 $1$。可以证明，这总是可行的。

你的任务是帮助尼古拉计算为了使所有盒子中姜饼数量的最大公约数变为 $1$，需要添加的最少姜饼数量。

输入格式

第一行包含一个整数 $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$ 盒最初的姜饼数量。

输出格式

输出一行，包含一个整数，表示尼古拉需要添加到盒子中的最少姜饼数量。如果无需添加任何姜饼即可使最大公约数为 $1$，则输出 $0$。

样例

输入

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$），这些都不够。添加两块姜饼，例如一块到第一盒，一块到第二盒，得到 $91$, $85$, $140$，GCD 为 $1$，因此答案为 $2$。注意，将两块姜饼都加到第一盒无济于事，得到 $92$, $84$, $140$，GCD 为 $4$。

数据范围与提示

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