Palindromic Permutation

Given an array of integers, determine whether it can be rearranged to form a palindrome. A palindrome is a sequence that reads the same backwards as forwards. In mathematical terms, a permutation of the array can form a palindrome if and only if the number of elements with an odd frequency is less than or equal to one, i.e., (\text{odd_count} \le 1).

For example, the array [1, 2, 2, 1] can form a palindrome since both 1 and 2 appear an even number of times, whereas the array [1, 2, 3, 2, 4] cannot because more than one element appears an odd number of times.

inputFormat

The input starts with an integer (T) denoting the number of test cases. For each test case, the first line contains an integer (M) representing the number of elements, and the second line contains (M) space-separated integers.

outputFormat

For each test case, output a single line containing 1 if the array can be rearranged to form a palindrome, or 0 otherwise.## sample

1
4
1 2 2 1

1