该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

黑板上写有 $N(\le200000)$ 个整数 $A_1, A_2, A_3, \dots, A_N$。
你需要进行 $N-1$ 次如下操作：

• 从黑板上选出两个数并将其擦去。记被擦去的数为 $x$ 和 $y$，然后将 $\gcd(x, y)$ 或 $\min(x, y)$ 中的一个写回黑板。

经过 $N-1$ 次操作后，黑板上只会剩下一个整数。请问，作为最后剩下的整数去重以后有多少个？

Format

Input

本题每个测试点包含不超过 4 组测试数据。

每个测试点的 $\sum n\le200000$ 。

除 $n$ 以外的所有正整数的和不超过 $2\times10^{13}$ 。

对于每组数据：

第一行一个正整数 $N$ 。

第二行 $N$ 个不超过 $10^9$ 的正整数。

Output

在一行中输出答案。

Samples

6
1 1 4 5 1 4

1

Limitation

1s, 1024KiB for each test case.