GCD Rearrangement Problem

You are given an integer n and a list of n positive integers. Your task is to determine whether it is possible to rearrange the list such that for every pair of consecutive numbers, their greatest common divisor (GCD) is greater than 1.

Recall that the GCD of two integers \(a\) and \(b\) is the largest positive integer that divides both \(a\) and \(b\). The condition is satisfied if there exists at least one prime number that divides at least two of the given numbers.

If such a rearrangement is possible, output YES; otherwise, output NO.

Note: You are required to read input from stdin and write output to stdout.

inputFormat

The first line contains a single integer \(n\), the number of integers in the list. The second line contains \(n\) space-separated positive integers.

Example:

4
4 6 3 9

outputFormat

Output a single line containing either YES if it is possible to rearrange the array satisfying the GCD condition, or NO otherwise.

## sample

4
4 6 3 9

YES

</p>