Almost Palindrome Verification

In this problem, you are given a string ( s ) and you must determine if it can be transformed into a palindrome by removing at most one character. A palindrome is a string that reads the same forwards and backwards. Formally, a string ( s ) is a palindrome if ( s = s^R ), where ( s^R ) is the reverse of ( s ).

Your task is to implement an algorithm that checks if the given string is an "almost palindrome". That is, the string is either already a palindrome or can become one by removing a single character.

For example, given the string "abca", removing the character 'b' or 'c' results in "aca" or "aba", both of which are palindromes.

inputFormat

The first line of the input contains an integer ( T ) (( 1 \leq T \leq 100 )), representing the number of test cases. Each of the following ( T ) lines contains a non-empty string ( s ) whose length does not exceed ( 10^5 ). The string consists of lowercase English letters only.

outputFormat

For each test case, output a single line containing either “True” if the string can be transformed into a palindrome by removing at most one character, or “False” otherwise.## sample

3
a
abc
abca

True
False
True