PUCMM001 - Good Arrays

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

Added by:kojak_
Date:2013-03-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:2013 Open PUCMM Beginners (Round #1)

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.