바이트랜드 재건

전쟁으로 무너진 바이트랜드를 다시 세우는 중이다. 마지막으로 남은 일은 우편 체계를 정리하는 것이다. 도시마다 우편번호를 하나씩 붙이는데, 우편번호는 $10^9$ 이하의 양의 정수이고 서로 다른 도시는 서로 다른 번호를 받는다.

바이트랜드 우편국은 조금 특이하게 움직인다. 도시 $A$에서 도시 $B$로 편지를 곧바로 보내려면 두 도시의 우편번호에 1보다 큰 공약수가 있어야 한다. 모든 도시가 나머지 도시 전부로 편지를 곧바로 보낼 수 있어야 하므로, 어떤 두 도시를 골라도 두 우편번호의 최대공약수는 1보다 커야 한다.

새로 만든 반부패법이 조건을 하나 더 붙인다. 전체 도시의 절반보다 많은 도시를 어떻게 모으더라도, 그 도시들의 우편번호에는 1보다 큰 공약수가 없어야 한다. 다시 말해 최대공약수가 1이어야 한다.

우편국이 배정안을 하나 제출했다. 도시 수와 제출된 우편번호를 읽어서 이 배정안이 위 규칙을 모두 지키는지 판정하는 프로그램을 작성하라.

첫째 줄에 바이트랜드의 도시 수 $n$이 주어진다. ($4 \le n \le 100$)

다음 $n$개 줄에는 우편국이 $i$번째 도시에 배정한 우편번호 $c_i$가 한 줄에 하나씩 주어진다. ($1 \le c_i \le 10^9$)

배정된 번호가 서로 다르다는 보장은 없다.

배정안이 문제의 규칙을 모두 지키면 VALID를, 하나라도 어기면 INVALID를 출력한다.

규칙을 모두 지킨다는 것은 $n$개의 우편번호가 서로 다르고, 두 우편번호를 어떻게 골라도 최대공약수가 1보다 크며, $n/2$개보다 많은 도시를 어떻게 모아도 그 우편번호의 최대공약수가 1이라는 뜻이다.