Palindrome Transformation

You are given a string S consisting of lowercase English letters. Your task is to determine whether it is possible to rearrange the letters of S to form a palindrome. Additionally, you are allowed to remove at most one character from S before rearranging.

A string is a palindrome if it reads the same forwards and backwards. A necessary and sufficient condition for a string to be rearranged into a palindrome is that at most one character appears an odd number of times. In this problem, if the string does not meet this condition, you are allowed to remove one character and check again.

Formally, for a given string \(S\), you need to determine whether either:

• \(S\) can be rearranged to form a palindrome (i.e. at most one character has an odd frequency), or
• There exists an index \(i\) (\(0 \le i < |S|\)) such that the string \(S\) with its \(i\)-th character removed can be rearranged to form a palindrome.

Output 1 if it is possible, or 0 if it is not.

inputFormat

The first line of input contains a single integer T (\(1 \le T \le 10^5\)), the number of test cases.

Each of the next T lines contains a non-empty string S consisting of lowercase English letters.

outputFormat

For each test case, output a single line containing the integer 1 if the string can be rearranged into a palindrome by removing at most one character, or 0 otherwise.

## sample

3
abca
racecar
abcdef

1
1
0

</p>