Palindrome Permutation Checker

Given an array of integers, determine whether the array can be rearranged to form a palindrome. In other words, you must decide if the whole array is a permutation of a palindrome. A string (or sequence) is a palindrome if it reads the same forwards and backwards. A necessary and sufficient condition for a set of elements to be rearranged into a palindrome is that at most one type of element has an odd frequency. Formally, if the frequency of each distinct element is (f_i), then the array is a permutation of a palindrome if and only if (\sum_{i} [f_i \mod 2 = 1] \leq 1).

inputFormat

The first line contains an integer (T) denoting the number of test cases. Each test case consists of two lines. The first line of a test case contains a single integer (N), the number of elements in the array. The second line contains (N) space-separated integers representing the array elements.

outputFormat

For each test case, output a single line with the word "YES" if the array can be rearranged to form a palindrome and "NO" otherwise.## sample

2
3
1 2 2
4
1 2 2 3

YES
NO