小 C 有一个长度为 n 的序列 A。

小 C 认为一个序列 A 是团结的当且仅当 \gcd(A_1,A_2,...,A_n)=1。

小 C 现在可以做以下操作任意次：

• 选择一个位置 i，将 A_i 变为 \gcd(A_i,i)，花费的代价为 n-i+1。

小 C 想求出使序列 A 团结的最小代价和。

输入的第一行包含一个整数 n。

接下来一行包含 n 个整数，第 i 个整数表示 A_i。

输出共一行，包含一个整数，表示最小代价和。

样例 1 解释

花费代价 2 选择位置 1，A_1 变为 1。

• 对于 30\% 的数据，保证 n\le 20。
• 对于 60\% 的数据，保证 n\le 50。
• 对于 100\% 的数据，1\le n\le 10^5，1\le A_i\le 10^9。

问题