Palindrome Rearrangement

You are given a string s. Your task is to determine whether the characters of s can be rearranged to form a palindrome.

A string can be rearranged into a palindrome if and only if at most one character appears an odd number of times. More formally, let \( f(c) \) denote the frequency of character \( c \) in s. Then s can be rearranged into a palindrome if and only if \[ \sum_{c}\mathbf{1}_{\{f(c)\ \text{is odd}\}} \le 1. \]

For each test case, output True if it is possible to rearrange the string to form a palindrome, or False otherwise.

inputFormat

The first line of input contains an integer t representing the number of test cases.

Each of the following t lines contains a non-empty string s consisting of lowercase and/or uppercase letters.

Input is provided via standard input (stdin).

outputFormat

For each test case, output a single line containing True if the characters of the string can be rearranged to form a palindrome, and False otherwise.

Output should be written to standard output (stdout).

## sample

3
civic
ivicc
hello

True
True
False

</p>