An array satisfies the PRIME-3 property if all of its elements are divisible any 3 distinct prime numbers. If a, b and c are primes that divide an element of the array, another set could divide another element and this would not violate the PRIME-3 property.

Lucy, a Computer Science student from your school, decided that an array that satisfies the PRIME-3 property is a Good Array. Given the description of an array, determine whether it is good.

Input

The input contains two lines. The first line contains a positive integer n (1 <= n <= 50), the size of the array. The following line contains n space-separated positive integers N_i. It is guaranteed that these integers will be in the range of [1, 2310].

Output

If the array satisfies the PRIME-3 property, output “YES”. If not, please output “NO”. In any case, please do not include quotes in your output!

Example

Input:
1
5

Output:
NO

Input:
3
30 105 385

Output:
YES