题目描述

Vlad 得到一个长度为 $n$ 的正整数数组 $a$。现在他想用它构造一个长度为 $n$ 的“美丽数组” $b$。

Vlad 认为一个数组是美丽的，当且仅当数组中所有数都是正数，并且具有相同的奇偶性。也就是说，所有数都大于零，并且要么全是偶数，要么全是奇数。

为了构造数组 $b$，Vlad 可以将每个 $b_i$ 赋值为 $a_i$，或者 $a_i - a_j$，其中 $j$ 可以是 $1$ 到 $n$ 中的任意一个数。

为了避免做不可能的事情，Vlad 想让你判断，是否有可能用数组 $a$ 构造出一个长度为 $n$ 的美丽数组 $b$。

输入格式

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

接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示数组 $a$ 的元素。

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

输出格式

输出 $t$ 行，每行对应一个测试用例的答案。如果 Vlad 能够构造出美丽数组 $b$，输出 "YES"；否则输出 "NO"。

答案不区分大小写（例如 "yEs"、"yes"、"Yes" 和 "YES" 都被认为是正确的正面回答）。

说明/提示

由 ChatGPT 4.1 翻译

样例

7
5
2 6 8 4 3
5
1 4 7 6 9
4
2 6 4 10
7
5 29 13 9 10000001 11 3
5
2 1 2 4 2
5
2 4 5 4 3
4
2 5 5 4

NO
YES
YES
YES
YES
NO
NO