Identify Palindromes

You are given a set of strings. Your task is to determine for each string whether it is a palindrome. A string is considered a palindrome if, after removing all non-alphanumeric characters and ignoring case differences, it reads the same forward and backward.

For example, the phrase "A man a plan a canal Panama" is a palindrome.

You need to process input from standard input (stdin) and output your results to standard output (stdout). Each result should be printed on a new line as either "Palindrome" or "Not a Palindrome" corresponding to each input string.

Note: When cleaning the string, consider only alphanumeric characters and ignore spaces, punctuation, and capitalization. Use the following formula for cleaning:

\( cleanedString = \text{lower}\big(\text{removeNonAlphanumeric}(s)\big) \)

inputFormat

The input begins with an integer \( n \) representing the number of strings. Each of the next \( n \) lines contains one string.

Example:

5
A man a plan a canal Panama
No lemon, no melon
Hello world
Was it a car or a cat I saw
not a palindrome

outputFormat

For each input string, output "Palindrome" if the cleaned string is a palindrome; otherwise output "Not a Palindrome". Each output should be on its own line.

Example:

Palindrome
Palindrome
Not a Palindrome
Palindrome
Not a Palindrome

## sample

5
A man a plan a canal Panama
No lemon, no melon
Hello world
Was it a car or a cat I saw
not a palindrome

Palindrome
Palindrome
Not a Palindrome
Palindrome
Not a Palindrome

</p>