Người yêu của FullHouse Dev

Trong một buổi hẹn hò lãng mạn, FullHouse Dev và người yêu của mình đã quyết định thử thách nhau bằng một bài toán thú vị về mảng và palindrome. Họ cùng nhau nghiên cứu và giải quyết vấn đề này, tận hưởng niềm vui của việc lập trình cùng nhau.

Bài toán

Cho một mảng gồm \(n\) số nguyên. Bạn cần biến đổi mảng này, với mỗi phần tử \(a_i\): \(a_i = a_i \bmod 2\). Ví dụ: nếu mảng ban đầu là 3, 4, 5 thì sau khi biến đổi, mảng sẽ trở thành 1, 0, 1.

Nhiệm vụ của bạn là kiểm tra xem có thể sắp xếp lại các phần tử của mảng đã biến đổi để tạo thành một palindrome hay không.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng bộ test.
• Với mỗi bộ test:
  • Dòng đầu tiên chứa số nguyên \(n\) - số lượng phần tử trong mảng.
  • Dòng thứ hai chứa \(n\) số nguyên - các phần tử của mảng.

OUTPUT FORMAT:

• Với mỗi bộ test, in ra 1 nếu có thể biến đổi mảng thành palindrome, ngược lại in ra 0.

Ràng buộc:

• \(1 \leq T \leq 100\)
• \(1 \leq n \leq 10^5\)
• \(1 \leq a_i \leq 10^9\)

Ví dụ

INPUT

2
3 
1 5 7
6
1 2 3 3 3 3

OUTPUT

1
0

Giải thích

• Ở bộ test đầu tiên, sau khi biến đổi, mảng sẽ trở thành 1, 1, 1. Mảng này đã là một palindrome, nên kết quả là 1.
• Ở bộ test thứ hai, sau khi biến đổi, mảng sẽ trở thành 1, 0, 1, 1, 1, 1. Không có cách nào sắp xếp lại các phần tử này để tạo thành palindrome, nên kết quả là 0.