Division Expression

Time limit1sMemory limit128 MB

Summary

Given a left-to-right division expression of n positive integers, decide if some parenthesization yields an integer value, which reduces to checking if x1 times the product of x3..xn is divisible by x2.

Level: Medium4 of 10
Topics: Math, Number theory, Greedy
Solved: No attempts yet

Problem

A division expression is an arithmetic expression of the form

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

where each $x_i$ is a positive integer for $1 \le i \le k$ . A division expression is evaluated from left to right. For instance, the value of

$1/2/1/2$

is $1/4$ .

You may insert parentheses into the expression to change its value. For example, the value of

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

is $1$ .

You are given a division expression $E$ . Decide whether it is possible to insert parentheses into $E$ to obtain an expression $E'$ whose value is an integer.

Write a program that, for each data set in a sequence of data sets, reads an expression $E$ , determines whether some placement of parentheses makes its value an integer, and reports the result.

Input

The first line contains one positive integer $d$ ( $d \le 5$ ), the number of data sets. The data sets follow.

The first line of each data set contains an integer $n$ ( $2 \le n \le 10000$ ), the number of integers in the expression. Each of the next $n$ lines contains exactly one positive integer no greater than $1\,000\,000\,000$ ; the $i$ -th of these is $x_i$ , the $i$ -th integer in the expression.

Output

For each data set, print on its own line YES if the expression can be parenthesized so that its value is an integer, and NO otherwise.

Examples3

Example 1
Input
```
2
4
1
2
1
2
3
1
2
3
```
Expected output
```
YES
NO
```
Example 2
Input
```
1
2
6
3
```
Expected output
```
YES
```
Example 3
Input
```
1
2
3
6
```
Expected output
```
NO
```