题目描述

你是一名见习炼金术士。为了通过毕业考核，你需要熬制一瓶“纯粹魔药”。

在你面前有 $m$ 种魔法材料，每种材料当前的“魔力浓度”为一个正整数，依次记为 $v_1, v_2, \dots, v_m$。

你可以对这些材料进行一种叫做“提纯”的魔法操作。每次你可以选择任意一种材料，并对其施放提纯魔法：

• 如果该材料当前的魔力浓度为 $x$，施法后，它的魔力浓度会变成 $x$ 的正约数的个数 $d(x)$。

例如：如果浓度为 $6$，因为 $6$ 有 $1, 2, 3, 6$ 共四个约数，提纯后浓度变为 $4$。

你可以对任意材料进行任意次提纯操作（也可以不操作）。

根据炼金术法则，只有当这 $m$ 种材料的魔力浓度之乘积恰好是一个质数（即只能被 $1$ 和它本身整除的大于 $1$ 的整数，如 $2, 3, 5$ 等）时，纯粹魔药才能熬制成功。

现在，请判断你是否有可能通过若干次操作，成功熬制出纯粹魔药。

输入格式

第一行包含一个整数 $T$，表示测试数据的组数。

对于每组测试数据：

• 第一行包含一个整数 $m$，表示魔法材料的数量。
• 第二行包含 $m$ 个整数 $v_1, v_2, \dots, v_m$，表示每种材料的初始魔力浓度。

输出格式

对于每个测试数据，如果能够使最终所有材料的魔力浓度乘积变为质数，输出 YES；否则输出 NO。

2
3
1 6 1
4
1 1 1 1

YES
NO

提示

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$1 \leq T \leq 10$，$1 \leq m \leq 10$，$1 \leq v_i \leq 100$；

对于所有评测用例，$1 \leq T \leq 1000$，$1 \leq m \leq 10^5$，$1 \leq v_i \leq 10^{18}$，且保证对于所有的测试数据，$m$ 的总和不超过 $2 \times 10^5$。