Equalizing Sequence with Multiplicative Operations

You are given a sequence of n positive integers \(a_1, a_2, \ldots, a_n\). You must choose an integer \(k\) such that \(1\le k\le n\) at the beginning. Then, you are allowed to perform the following operation arbitrarily many times:

• Select exactly \(k\) distinct positions in the sequence.
• Multiply the numbers at all the chosen positions by the same nonzero integer (this integer can be positive or negative).

Your goal is to make all numbers in the sequence equal. Determine the maximum \(k\) (with \(1\le k\le n\)) for which it is possible to eventually obtain a sequence of equal numbers.

Note: In each operation the multiplier must be a nonzero integer. Also, if the elements are already equal then any \(k\) is valid, so the answer is \(n\) in that case.

It can be shown that, by considering the prime factorizations of the numbers, a necessary and sufficient condition for a chosen \(k\) to work is that for every prime \(p\) the following holds. Let \(v_p(a_i)\) denote the exponent of \(p\) in \(a_i\). Define \[ M_p = \max_{1\le i\le n} v_p(a_i)\quad \text{and} \quad S_p = \sum_{i=1}^n v_p(a_i). \] Then there must exist a nonnegative integer \(t\) (which can depend on \(p\)) satisfying \[ n(M_p+t)-S_p \equiv 0 \pmod{k}. \] Since \(n\) always divides \(n(M_p+t)-S_p\) except for a remainder induced by \(S_p-nM_p\), one can show that a necessary and sufficient condition is that \[ \gcd(n,k) \mid (S_p - nM_p)\quad \text{for every prime}\; p. \]

Your task is to output the maximum \(k\) (\(1\le k\le n\)) such that the above condition holds for every prime that appears in the factorization of at least one of \(a_1, a_2, \ldots, a_n\).

inputFormat

The first line contains a single integer \(n\) \((1\le n\le 10^5)\), the length of the sequence.

The second line contains \(n\) positive integers \(a_1, a_2, \ldots, a_n\) \((1 \le a_i \le 10^9)\) separated by spaces.

outputFormat

Output a single integer: the maximum valid \(k\) for which it is possible to make all the numbers in the sequence equal using the allowed operations.

sample

2
2 2

2