该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Calin 有 $n$ 个桶，第 $i$ 个桶里装有 $a_i$ 个边长为 $1$ 的木质小正方形（即 $1\times 1$ 方块）。

Calin 想用所有给定的小正方形拼成一个大正方形（边长为整数）。问是否可行？

输入格式

第一行一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数量。

每个测试用例包含两行：

• 第一行一个整数 $n$（$1 \le n \le 2\cdot 10^5$），表示桶的数量。
• 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1 \le a_i \le 10^9$），表示每个桶中的 $1\times 1$ 方块数量。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

输出格式

对每个测试用例输出一行：

• 如果能用所有 $1\times 1$ 方块拼成一个大正方形，输出 YES；
• 否则输出 NO。

说明：本题输出大小写原题允许任意，但为适配固定判题平台，本题要求严格输出大写 YES 或 NO。

样例

输入

5
1
9
2
14 2
7
1 2 3 4 5 6 7
6
1 3 5 7 9 11
4
2 2 2 2

输出

YES
YES
NO
YES
NO

说明

• 第 1 组：总数 $9$，可拼成 $3\times 3$。
• 第 2 组：总数 $16$，可拼成 $4\times 4$。
• 第 3 组：无法用全部方块拼成正方形。