Problem B
Batch GCD

As we know, the security of the RSA problem relies on the difficulty of factoring integers. Generally, the RSA modulus is generated as follows:

• Pick two large prime integers $p$ and $q$,

• Compute $n = p \cdot q$.

Generally speaking, if $p$ and $q$ are large enough (e.g. $1024$-bit primes), then it is infeasible to factorize $n$, which is our only known strategy to break the security of RSA.

The problem with this strategy, however, is that if we have two modulus $n = p \cdot q$ and $n’ = p \cdot q’$ for $q \ne q’$, then we can compute $p = \gcd (n, n’)$, thus factoring both $n$ and $n’$. See https://crypto.stackexchange.com/q/76757 for some recent researches on this topic, the most recent research can factors $1$ in $172$ in RSA certificates.

Usually, the cause of such collision is poor randomization in the devices used to generate the random primes. Some ways to mitigate the issue is discussed in the question linked above.

If you have a huge collection of, for example, 340 million integers, it would be completely infeasible to compute the $\gcd $ of each pair. Instead, a batch GCD algorithm is needed. Common implementation of that algorithm is the following:

• Divide the set of modulus into two sets $A$ and $B$ of roughly equal sizes.

• Use divide and conquer, compute the product $\prod A$ of all elements in $A$, as well as the product $\prod B$ of all elements in $B$.

  Using one of the fast integer multiplication algorithms based on FFT, this step can be done in time $\tilde O(n)$, where $n$ is the total number of bits representing the numbers in the input.

• Compute $\gcd (\prod A,\prod B)$. With the half-GCD algorithm, this step can also be done in time $\tilde O(n)$.

If there’s any pair $a\in A$, $b\in B$ with $\gcd (a, b)>1$, this algorithm would detect that pair. Otherwise, the algorithm recurses down to the sets $A$ and $B$.

In this problem, you will be solving a much simpler instance with smaller size of integers: Given $n$ integers $a_1, a_2, \dots , a_ n$, determine if there exists any pair with $\gcd (a_ i, a_ j)>1$.

Input

The first line contains a positive integer $n \le 10^6$, the second line contains $n$ positive integers $a_ i \le 10^{10}$.

Output

For each test case, print the string “YES” or “NO” on a line.

1
2

NO

2
1 1

NO

2
2 2

YES

3
6 10 15

YES