나눗셈 식

시간 제한1초메모리 제한128 MB

요약

왼쪽부터 나눗셈으로 이어지는 n개의 양의 정수 수식에서 괄호를 적절히 넣어 값을 정수로 만들 수 있는지 판별하는 문제이며, x1과 x3부터 xn까지의 곱이 x2로 나누어지는지 확인하는 것으로 귀결됩니다.

난이도: 보통10점 중 4점
유형: 수학, 정수론, 그리디
정답자: 아직 제출이 없습니다

문제

나눗셈 식은 다음과 같은 형태의 산술식이다.

$x_1 / x_2 / x_3 / \cdots / x_k$

여기서 각 $x_i$ 는 양의 정수이다( $1 \le i \le k$ ). 나눗셈 식은 왼쪽에서 오른쪽으로 계산한다. 예를 들어

$1/2/1/2$

의 값은 $1/4$ 이다.

식에 괄호를 넣어 값을 바꿀 수 있다. 예를 들어

$(1/2)/(1/2)$

의 값은 $1$ 이다.

나눗셈 식 $E$ 가 주어진다. $E$ 에 괄호를 적절히 넣어 값이 정수가 되는 식 $E'$ 을 만들 수 있는지 판정하여라.

여러 개의 데이터 집합이 주어질 때, 각 데이터 집합마다 식 $E$ 를 읽고, 괄호를 적절히 넣어 값을 정수로 만들 수 있는지 판정하여 결과를 출력하는 프로그램을 작성하여라.

입력

첫째 줄에 데이터 집합의 개수를 나타내는 양의 정수 $d$ ( $d \le 5$ )가 주어진다. 그 뒤로 데이터 집합들이 이어진다.

각 데이터 집합의 첫째 줄에는 식에 포함된 정수의 개수 $n$ ( $2 \le n \le 10000$ )이 주어진다. 이어지는 $n$ 개의 줄에는 각각 $1\,000\,000\,000$ 이하의 양의 정수가 하나씩 주어지며, $i$ 번째 수가 식의 $i$ 번째 정수 $x_i$ 이다.

출력

각 데이터 집합에 대해, 괄호를 적절히 넣어 값을 정수로 만들 수 있으면 YES를, 그렇지 않으면 NO를 한 줄에 하나씩 출력한다.

예제3

예제 1
입력
```
2
4
1
2
1
2
3
1
2
3
```
예상 출력
```
YES
NO
```
예제 2
입력
```
1
2
6
3
```
예상 출력
```
YES
```
예제 3
입력
```
1
2
3
6
```
예상 출력
```
NO
```