Check Palindrome Strings

You are given n strings. For each string, determine if it is a palindrome.

A string is considered a palindrome if, after removing all non-alphanumeric characters and ignoring case, it reads the same forwards and backwards. For example, "A man a plan a canal Panama" is a palindrome.

Your task is to process each string and output "Palindrome" if the string is a palindrome, or "Not Palindrome" otherwise.

Note: The input will be given via standard input, and the output should be printed to standard output.

inputFormat

The first line of the input contains a single integer n representing the number of strings.

This is followed by n lines, each containing one string.

Input Format:

n
s1
s2
...
sn

outputFormat

For each of the n strings given as input, print a line containing either "Palindrome" or "Not Palindrome" according to whether the string is a palindrome (ignoring case and non-alphanumeric characters).

Output Format:

result1
result2
...
resultn

## sample

5
racecar
hello
A man a plan a canal Panama
Was it a car or a cat I saw
Not a palindrome

Palindrome
Not Palindrome
Palindrome
Palindrome
Not Palindrome

</p>