Problem Description

You are an apprentice alchemist. To pass the graduation assessment, you need to brew a bottle of “Pure Magic Potion”.

In front of you there are $m$ kinds of magic materials. The current “magic concentration” of each material is a positive integer, denoted in order as $v_1, v_2, \dots, v_m$.

You can perform a magic operation called “refining” on these materials. Each time, you may choose any one material and cast the refining spell on it:

• If the material’s current magic concentration is $x$, then after casting, its magic concentration becomes the number of positive divisors of $x$, denoted as $d(x)$.

For example: if the concentration is $6$, since $6$ has $1, 2, 3, 6$ in total four divisors, after refining the concentration becomes $4$.

You may refine any material any number of times (or not refine it at all).

According to the rules of alchemy, the Pure Magic Potion can be brewed successfully only when the product of the magic concentrations of these $m$ materials is exactly a prime number (that is, an integer greater than $1$ that is divisible only by $1$ and itself, such as $2, 3, 5$, etc.).

Now, determine whether it is possible, through some number of operations, to successfully brew the Pure Magic Potion.

Input Format

The first line contains an integer $T$, the number of testdata sets.

For each testdata set:

• The first line contains an integer $m$, the number of magic materials.
• The second line contains $m$ integers $v_1, v_2, \dots, v_m$, representing the initial magic concentration of each material.

Output Format

For each testdata set, if you can make the product of the final magic concentrations of all materials become a prime number, output YES; otherwise output NO.

2
3
1 6 1
4
1 1 1 1

YES
NO

Hint

Constraints

For $30\%$ of the testdata, $1 \leq T \leq 10$, $1 \leq m \leq 10$, $1 \leq v_i \leq 100$.

For all testdata, $1 \leq T \leq 1000$, $1 \leq m \leq 10^5$, $1 \leq v_i \leq 10^{18}$, and it is guaranteed that for all testdata, the sum of $m$ does not exceed $2 \times 10^5$.

Translated by ChatGPT 5