A palindrome sentence is a sentence that forms a palindrome when only the letters of the sentence are taken into account. All characters in the sentence that are not a letter (e.g. spaces and punctuation marks) are ignored. Furthermore, no distinction is made between uppercase and lowercase letters. An example of a palindrome sentence is"A man, a plan, a canal: Panama".

Input

The first line of the input contains an integer $$t$$ that indicates how many test cases there are. The next $$t$$ lines of input each contain one sentence.

Output

For each of the sentences from the input: (palindrome sentence) or (not a palindrome sentence).

Example

Input:

2
A man, a plan, a camel: Panama!
A man, a plan, a canal: Panama!

Output:

not a palindrome sentence
palindrome sentence