310969: CF1915C. Can I Square?

C. Can I Square?time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Calin has $n$ buckets, the $i$-th of which contains $a_i$ wooden squares of side length $1$.

Can Calin build a square using all the given squares?

Input

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of buckets.

The second line of each test case contains $n$ integers $a_1, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the number of squares in each bucket.

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output "YES" if Calin can build a square using all of the given $1 \times 1$ squares, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

ExampleInput

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

Output

YES
YES
NO
YES
NO

Note

In the first test case, Calin can build a $3 \times 3$ square.

In the second test case, Calin can build a $4 \times 4$ square.

In the third test case, Calin cannot build a square using all the given squares.

题目大意：
卡拉拥有n个桶，第i个桶里有a_i个边长为1的木块。问卡拉能否用所有的木块恰好拼成一个正方形。

输入数据格式：
第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。
每个测试用例的第一行包含一个整数n（1≤n≤2×10^5），表示桶的数量。
每个测试用例的第二行包含n个整数a_1, ..., a_n（1≤a_i≤10^9），表示每个桶里的木块数量。
所有测试用例的n之和不超过2×10^5。

输出数据格式：
对于每个测试用例，如果卡拉可以用所有的1×1木块拼成一个正方形，输出"YES"，否则输出"NO"。
答案不区分大小写，例如"yEs"、"yes"、"Yes"和"YES"都会被认定为肯定的回答。

示例：
输入：
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

说明：
第一个测试用例，卡拉可以拼成一个3×3的正方形。
第二个测试用例，卡拉可以拼成一个4×4的正方形。
第三个测试用例，卡拉无法用所有的木块拼成一个正方形。题目大意： 卡拉拥有n个桶，第i个桶里有a_i个边长为1的木块。问卡拉能否用所有的木块恰好拼成一个正方形。 输入数据格式： 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。 每个测试用例的第一行包含一个整数n（1≤n≤2×10^5），表示桶的数量。 每个测试用例的第二行包含n个整数a_1, ..., a_n（1≤a_i≤10^9），表示每个桶里的木块数量。 所有测试用例的n之和不超过2×10^5。 输出数据格式： 对于每个测试用例，如果卡拉可以用所有的1×1木块拼成一个正方形，输出"YES"，否则输出"NO"。 答案不区分大小写，例如"yEs"、"yes"、"Yes"和"YES"都会被认定为肯定的回答。 示例： 输入： 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 说明： 第一个测试用例，卡拉可以拼成一个3×3的正方形。 第二个测试用例，卡拉可以拼成一个4×4的正方形。 第三个测试用例，卡拉无法用所有的木块拼成一个正方形。