Reconstruction of Byteland

Byteland is being rebuilt after a devastating war, and the last job left is the postal system. Every city gets one postal code, a positive integer not greater than $10^9$, and two cities never share the same code.

The Bytean Postal Service works in a strange way. A letter goes directly from city $A$ to city $B$ only when the postal codes of the two cities have a common divisor greater than 1. Every city must be able to send a letter directly to every other city, so for any two cities the greatest common divisor of their codes has to be greater than 1.

The new anti-corruption law adds one more condition. Take any set of cities that holds more than half of all the cities. The postal codes in that set must have no common divisor greater than 1, so their greatest common divisor is exactly 1.

The postal service has already handed in one assignment. Write a program that reads the number of cities and the proposed postal codes, then decides whether the assignment obeys every rule above.

The first line contains one integer $n$, the number of cities of Byteland ($4 \le n \le 100$).

Each of the next $n$ lines contains one integer $c_i$, the postal code that the postal service proposes for the $i$-th city ($1 \le c_i \le 10^9$).

The proposed codes are not guaranteed to be different from one another.

Print VALID if the proposed assignment follows every rule of the statement, and INVALID if it breaks any of them.

Following every rule means that the $n$ postal codes are pairwise different, that any two codes have greatest common divisor greater than 1, and that any set of more than $n/2$ cities has codes whose greatest common divisor is 1.