Sign Inversion

Cho một mảng $a$ gồm $n$ phần tử, mỗi phần tử chỉ nhận giá trị $-1$ hoặc $1$.

Bạn có thể thực hiện thao tác sau trên mảng $a$ với số lần tùy ý:

• Chọn một chỉ số $i$ thỏa mãn $1 ≤ i ≤ n - 1$.
• Gán $a_i = -a_i$ và $a_{i + 1} = -a_{i + 1}$.

Hãy xác định xem có thể làm cho tổng các phần tử của mảng $a$ bằng $0$ hay không.

Dữ liệu vào

Mỗi bộ test gồm nhiều test case. Dòng đầu tiên chứa số lượng test case $t$ ($1 ≤ t ≤ 200$). Mô tả của các test case theo sau.

Dòng đầu tiên của mỗi test case chứa một số nguyên $n$ ($1 ≤ n ≤ 100$) là độ dài của mảng $a$.

Dòng thứ hai của mỗi test case chứa $n$ số nguyên $a_1, a_2, ..., a_n$ ($a_i \in {-1, 1}$) là các phần tử của mảng $a$.

Kết quả

Với mỗi test case, in ra "YES" nếu có thể làm cho tổng các phần tử của mảng $a$ bằng $0$, ngược lại in ra "NO".

Bạn có thể in ra câu trả lời ở bất kỳ định dạng chữ hoa hay chữ thường nào. Ví dụ, các chuỗi "yEs", "yes", "Yes" và "YES" đều được chấp nhận là câu trả lời khẳng định.

Chấm điểm

Subtask 1 (30 points). $n ≤ 12$

Subtask 2 (70 points). $1 ≤ t ≤ 200$; $1 ≤ n ≤ 100$

Ví dụ

Input

5
1
-1
2
1 -1
2
1 1
5
1 -1 1 -1 1
6
-1 1 -1 -1 -1 -1

Output

NO
YES
NO
NO
YES

Ghi chú

Trong test case đầu tiên, chúng ta không thể thực hiện bất kỳ thao tác nào và tổng các phần tử của $a$ bằng $-1 ≠q 0$, do đó câu trả lời là "NO".

Trong test case thứ hai, tổng các phần tử của $a$ đã bằng $0$, do đó câu trả lời là "YES".

Trong test case thứ năm, chúng ta có thể thực hiện một thao tác với $i = 3$, biến đổi $a$ như sau: $[-1, 1, -1, -1, -1, -1] \rightarrow [-1, 1, 1, 1, -1, -1]$. Tổng của mảng thu được bằng $0$, do đó câu trả lời là "YES".