以下 \(M = \max(A)\) とします。

まず \(G\) を求めましょう。しかし、すべての部分集合に対して求めるのは現実的ではありません。ここで

• \(S\) の要素がすべて \(G\) で割り切れる \(\iff\) ある集合 \(S\) の \(\gcd\) が \(G\) の倍数である

が成り立つことを利用します。（証明はそこまで難しくないため、省略させてください）

つまり、ある \(g\) の倍数が \(2\) つ以上存在すれば、それを選んで \(S\) とすることで \(\gcd\) を \(g\) の倍数とできます。そして、このような \(g\) としてありうる最大値を求めれば、それが \(G\) であることもわかります。

これは、あらかじめ頻度列をつくっておけば、愚直に \(g\) の倍数をすべて舐めても、調和級数で抑えられて \(O(M \log M)\) で求めることができます。

とかなんとかいいましたが、実は答えは \(N-2\) です。

つまり、 \(G\) の倍数が \(3\) つ以上存在しても、そこから（適切にではなく）適当に \(2\) つ選べば、必ず \(\gcd\) は \(G\) になることが示せます。

上の議論から分かるとおり、一般的には「 \(\gcd\) が \(G\) の集合があるとき、その部分集合の \(\gcd\) は \(G\) の倍数である」ことまでしかわかりません。しかし、今回は \(G\) が \(\gcd\) の最大値ですから \(G\) より大きくなることはないため、 \(G\) 以外の値になることはありません。

実装例

n = int(input())
print(n - 2)