题目描述

托伦自中世纪以来就以其传统姜饼闻名。小尼古拉想在他最爱的店铺购买 $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

数据范围与提示

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